Tree Notes

• Dictionaries and sets can be implemented using hashtable. It uses constant amount of time on average for earehc insert delete

• Binary search tree can do operations like search, insert, delete, on log N time in worst case.

• Binary serach tree can do things like finding predecesaro/successor, min and max operations in log N time which hash table cannot do.

• Mostly tree traversal and reconstruction problems are divide and conquer type or brute force.

• Analogous of BFS for array is a straight forward for loop from start to end of the array.

• For every tree problem BFS or DFS, there is an edge case of if root is NULL return.

• DFS is analogus to divide and conquer whereas BFS is more analogus to brute force

• Should we check if node is null in the recursive code or in the parent code? This could be done but Omkar says chck base case only in the parent.

• In decision problems (example path sum) we can short circuit if we know true or false and need not go all the way to the leaf node.

• Top down dfs are those problems were leaf nodes need not return back results up but can update the global variable and return.

• For Top down dfs, we need to pass additional parameters too along with node info.

• Any problem that can be solved by BFS can be solved by Top Down DFS and vice versa. This applies only to Top Down DFS and not to bottom up dfs or other types of dfs problems.

  • For example, the path sum problem which is a top down dfs can be solved using BFS. In this approach, when the node is popped out and its children are gathered back into the queue, the slate and target sum are also packaged along with the children. Since the BFS is also going to flow down every level, the logic can be written to check the target sum for a given path.

  • Similarly, in top down dfs, the first node in the path is the leftmost and each time the path comes back to a given level, the next node to the right of the leftmost is processed. This can be used to do level wise traversal using top down dfs.

Tree Construction

• Most popular is top down.

• Figure out what the root should be and follow the lazy manager strategy of delegating the task of left subtree and right subtree to two subordinates.

• Once they return, assign the left child of root to the left subtree and right side of the root to the right subtree

• Height balanced of binary search tree means the height of left and right subtree should not differ by more than one for any node at any level.

• This is not the same with binary heaps. It had complete binary trees and all filled in except last level which is filled as far left as possible.

• Height balanced tree does not mean that at particular level we should have 2^i nodes (say in ith level). What is required is the height difference between any two subtrees for any given node should be atmost 1. This is a type of balanced binary search tree called AVL tree

• For AVL trees, the height can be above logN but below a constant logN. For example it can be above 1logN and below 2logN which is still ~O(logN)

• Reconstructing a binary tree from preorder and inorder traversal should assume that there are no duplicates. With duplicates, there could be more than one form of binary tree and so hard to reconstruct the binary tree.

• Tree reconstruction can be done from left to right instead of top to bottom.

References:

Interview Kickstart:

• Tree Series Videos