Binary Tree
Solve Tree Problems Recursively
"Top-down" Solution "Top-down" means that in each recursion level, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively. So the "top-down" solution can be considered as kind of preorder traversal.
1. return specific value for null node
2. update the answer if needed // anwer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, params
5. return the answer if needed // answer <-- left_ans, right_ans
"Bottom-up" Solution "Bottom-up" is another recursion solution. In each recursion level, we will firstly call the functions recursively for all the children nodes and then come up with the answer according to the return values and the value of the root node itself. This process can be regarded as kind of postorder traversal.
1. return specific value for null node
2. left_ans = bottom_up(root.left) // call function recursively for left child
3. right_ans = bottom_up(root.right) // call function recursively for right child
4. return answers // answer <-- left_ans, right_ans, root.val
Balanced Tree
The difference between heights of left subtree and right subtree is not more than 1.
Complete Tree
A complete binary tree is a binary tree in which every level of the tree is fully lled, except for perhaps the last level. To the extent that the last level is lled, it is lled left to right.
BFS v.s DFS
A Tree is typically traversed in two ways:
- Breadth First Traversal (Or Level Order Traversal)
- Depth First Traversals
- Inorder Traversal (Left-Root-Right)
- Preorder Traversal (Root-Left-Right)
- Postorder Traversal (Left-Right-Root)
All four traversals require O(n) time as they visit every node exactly once.
Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level.
Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.
Technique 1: Count the nodes at the current level
We can count the nodes at the current level. After pushing all children of the current level to the queue, the size of the queue is the same as the level count.
- Level Order Traversal
Technique 2: Store depth info
Sometimes we need to know the depth of the current processing node. There are two way to access depth info in O(1) time.
- Pass depth as parameter in recursive function
Save depth in hash map.
Level Order Traversal
Technique 3: Using two queue
We can insert the first level in first queue and print it and while popping from the first queue insert its left and right nodes into the second queue.
Technique 4: Recursive with return value and changing params
Sometimes we need to keep track of multiple things, we can utilize the recursive function return to keep track of one thing, and then passing parameter to remember something else.
- Find path to Node
- Binary Tree Path
- Lowest Common Ancestor
- Binary Tree Tilt
Technique 5: BFS v.s DFS
BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.
Technique 6: Lowest common ancestor
The key is to determine where the lca lies.
In binary tree, if root is equal to either node then we found the lca. We also need to check the situation where one node lies in the left subtree and the other one lies in the right subtree. If so, then the root is the lca.
Note: This solution assumes that both nodes are present in the tree, otherwise we need to check their existance.
In binary search tree, we can just check the value of nodes to decide where the lca lies. If both nodes are smaller than the root, then lca lies in the left subtree. If both nodes are larger than the root, then lca lies in the right subtree.
- Lowest Common Ancestor in Binary Tree
- Lowest Common Ancestor in Search Binary Tree