Binary trees are widely used data structures. Similar to linked lists, they are inductively defined: a binary tree node is comprised of a value and two child binary tree nodes, left and right. A binary tree can also be empty. The node that a child of no subtree is called the root. Binary trees are most useful in contexts where data has some kind of ordering since one can put the lesser nodes (with respect to a given node) on the left and the greater ones on the right. Binary trees tend to show up quite a bit in interviews because there are a lot of interesting problems you can ask about them. The key concept you need to learn is the many ones one can traverse a binary tree.
Tree in programming are more like family trees (without accounting for marriages) in that they grow downward. A diagram that lists your great great grandparent and all descendants would be a good example.
Consider the following binary tree:
1 / \ 2 3 / \ \ 4 5 6The four most prevalent traversal orders are:
- Preorder: 1 2 4 5 3 6
- Inorder: 4 2 5 1 3 6
- Postorder: 4 5 2 6 3 1
- Level order: 1 2 3 4 5 6
There is some basic terminology you need to have down cold:
- root: The node from which a binary tree emanates. It has no parent and all nodes in the tree are descendants of the root. Usually, we supply a root to a function to pass it the tree since you can access all the tree from the root.
- leaf: A node in a tree that has no children. Leaves from the bottom edge of a tree.
- subtree: A contiguous component of a tree consisting of a root of the subtree and all its descendants.
- descendant: a node B is said to be a descendant of another node A if one can reach B by following the child pointers from A and its children, descendants, etc.
Binary Tree Problems
Let's extend the binary tree definition with a fourth member, next, which will be a pointer to the adjacent sibling of a given node. Given the root of a binary tree with all the next members nulled out, write a function that fills in all the next members. For the rightmost side of the tree, the next member for each node should be null. So, for the following input:
1 / \ 2 3 / \ \ 4 5 6Your function should produce the following output:
1 -> null / \ 2-> 3 -> null / \ \ 4 ->5-> 6 -> null
- A binary tree is said to be symmetric if the left subtree from the root is the mirror of the right subtree in terms of both values and structure. Write a function that determines if a binary tree is symmetric.
- The lowest common ancestor (LCA) of two nodes in a tree is the node furthest from the root that is an ancestor of both nodes. Write a function that takes a tree and two nodes in that node as input. The function should return the LCA of the two nodes.
We still need to wrap up the list addition problem and stack and queue problems. Remember to practice these problems by using the procedural given in the problem solving checklist including doing a basic running time and space analysis.
Check out the local tech job openings in Chicago when you get a chance.