Tree
Study links
Notes
A tree is an undirected and connected acyclic graph.
Recursion is a common approach for trees. When you notice that the subtree problem can be used to solve the entire problem, try using recursion.
When using recursion, always remember to check for the base case, usually where the node is null.
When you are asked to traverse a tree by level, use breadth-first search.
Sometimes it is possible that your recursive function needs to return two values.
If the question involves summation of nodes along the way, be sure to check whether nodes can be negative.
You should be very familiar with writing pre-order, in-order, and post-order traversal recursively. As an extension, challenge yourself by writing them iteratively. Sometimes interviewers ask candidates for the iterative approach, especially if the candidate finishes writing the recursive approach too quickly.
Do check out the section on Trie, which is an advanced tree.
Corner cases
- Empty tree
- Single node
- Two nodes
- Very skewed tree (like a linked list)
Special Trees
Binary Tree
In-order traversal of a binary tree is insufficient to uniquely serialize a tree. Pre-order or post-order traversal is also required.
Binary Search Tree (BST)
In-order traversal of a BST will give you all elements in order.
Be very familiar with the properties of a BST and validating that a binary tree is a BST. This comes up more often than expected.
When a question involves a BST, the interviewer is usually looking for a solution which runs faster than O(n).
Recommended LeetCode questions
- Maximum Depth of Binary Tree
- Same Tree
- Invert/Flip Binary Tree
- Binary Tree Maximum Path Sum
- Binary Tree Level Order Traversal
- Serialize and Deserialize Binary Tree
- Subtree of Another Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Lowest Common Ancestor of BST