Tree Practice Problems
NOTE: come up with solutions in at least 2 ways, if possible. . Ideally recursively and iteratively.
Solutions python
Tree Construction
Insert into a Binary Search Tree Delete Node in a BST Flatten binary tree to a linked list This one is more of a tree reordering problem.
Do I have to solve this problem in a preorder way? If you solve this problem in a preorder traversal way, it doesn't work because (1) traversal needs to remember the previous node. (2) the nodes do not know if they are left child or right child. (3) It's a tree reordering problem, so the code can go into (a) preorder section, (b) inorder section (c) post order section.
The key to the problem is the root node (or local root node) needs to last right node from its left side, because that's the last node before the root's right node is called. So you can connect the root's right node to that node.
[LR].right = root.right;
root.right = root.left;
root.left = null;
Preorder
public void flatten(TreeNode root) {
if (root == null) return;
if (root.left == null && root.right == null) return; // leaf
TreeNode rightMost = getRightMost(root.left);
if (rightMost != null) {
rightMost.right = root.right;
root.right = root.left;
root.left = null;
}
flatten(root.right);
}
private TreeNode getRightMost(TreeNode node) {
if (node == null) return null;
if (node.right == null) return node;
return getRightMost(node.right);
}
Inorder
- In this case, there will be always the right-most child from the left subtree, because the left subtree is already visited and the work is done there.
public void flatten(TreeNode root) {
if (root == null) return;
if (root.left == null && root.right == null) return; // leaf
flatten(root.left);
if (root.left != null) {
TreeNode rightMost = getRightMost(root.left);
rightMost.right = root.right;
root.right = root.left;
root.left = null;
}
flatten(root.right);
}
Postorder
- Same as the inorder, there will be always the right-most child from the left subtree, because the left subtree is already visited and the work is done there.
- It returns the right most child from left subtree. If the rightmost node does not exsit, the left node is being returned, just like the previous logic.
public void flatten(TreeNode root) {
flattenTree(root);
}
private TreeNode flattenTree(TreeNode node) {
if (node == null) return null;
if (node.left == null && node.right == null) return node;
TreeNode leftChild = flattenTree(node.left);
TreeNode rightChild = flattenTree(node.right);
if (leftChild != null) {
leftChild.right = node.right;
node.right = node.left;
node.left = null;
}
if (rightChild != null) return rightChild;
else return leftChild;
}
Recursion practice
Count the number of nodes in the tree Max depth of a binary tree
Given a non-empty binary search tree - an ordered binary tree, return the minimum data value found in that tree.
[invert BT - Change the tree into its mirror image] (https://leetcode.com/problems/invert-binary-tree/) Same tree Validate binary search tree
For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.
Tree Traversal
Serialize and deserialize a binary tree
The point of this problem is understanding how to create a binary tree if it was given in a sequence of numbers instead of a tree.
One way is serializing in preorder and deserializing in preorder.
public String serialize(TreeNode root) {
StringBuffer buf = new StringBuffer();
serialize(root, buf);
buf.delete(0, 1);
return buf.toString();
}
private void serialize(TreeNode root, StringBuffer buf) {
if (root == null) {
buf.append(",1004");
return;
}
buf.append("," + root.val);
serialize(root.left, buf);
serialize(root.right, buf);
}
public TreeNode deserialize(String data) {
System.out.println(data);
if (data.isEmpty()) return null;
if (data.length() == 1) return new TreeNode(Integer.parseInt(data));
String[] strarr = data.split(",");
int[] nums = new int[strarr.length];
int i = 0;
for (String str : strarr) {
nums[i++] = Integer.parseInt(str);
}
return insert(nums);
}
private int index = -1;
private TreeNode insert(int[] nums) {
index++; // important to increment before the base case
if (nums[index] == 1004) {
return null;
}
TreeNode node = new TreeNode(nums[index]);
node.left = insert(nums);
node.right = insert(nums);
return node;
}
Another way to do it is in level order
public String serialize(TreeNode root) {
StringBuffer buf = new StringBuffer();
if (root == null) return buf.toString();
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
buf.append(String.valueOf(root.val));
while (!q.isEmpty()) {
int qsize = q.size();
for (int i = 0; i < qsize; i++) {
TreeNode polled = q.poll();
if (polled.left != null) {
q.add(polled.left);
buf.append("," + polled.left.val);
} else {
buf.append(",1004");
}
if (polled.right != null) {
buf.append("," + polled.right.val);
q.add(polled.right);
} else {
buf.append(",1004");
}
}
}
//buf.delete(0, 1);
return buf.toString();
}
private TreeNode insertLevelorder(int[] nums) {
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(nums[0]);
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
int qsize = queue.size();
TreeNode node = queue.poll();
int leftIndex = level * 2 + 1;
int rightIndex = level * 2 + 2;
if (leftIndex < nums.length && nums[leftIndex] != 1004) {
TreeNode left = new TreeNode(nums[leftIndex]);
node.left = left;
queue.add(left);
}
if (rightIndex < nums.length && nums[rightIndex] != 1004) {
TreeNode right = new TreeNode(nums[rightIndex]);
node.right = right;
queue.add(right);
}
level++;
}
return root;
}
Extra tree
BST Right Side View Convert BST to a greater tree LCA easy LCA medium