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.

  1. Pass depth as parameter in recursive function
  2. Save depth in hash map.

  3. 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

results matching ""

    No results matching ""