Trees/Tries
- Posted by Nandini
- ON 18 June 2016
Trees and Tries
Warm-up
- Find the height of a tree
- Hint: How would you calculate the height of a tree if you know the height of the left and right sub-trees? Remember, recursion is all about solving a similar but smaller problem
Regular
- Find the lowest common ancestor of two nodes in a binary tree (not binary search tree).
- Hint: If a node is the LCA of two nodes, would those nodes be in the left sub-tree or the right sub-tree?
- Print the nodes of a tree level by level. Print the nodes at even levels from left to right, and those at odd levels from right to left
- Hint: Not really a hint, but first write a program to just print the nodes by level
- You are given a set of strings ("abc", "axyz", "abcz", "abergf"). Find the longest prefix that occurs in at least 3 strings. Answer: "ab".
- Hint: Construct a trie!
Challenge (Optional)
Checkout TripleByte - Direct onsite interviews at top tech and startups
Check out our Advanced bootcamp (Recursion, Dynamic Programming, System/Object Design) on the weekend of August 5/6.