Binary trees is one of the favorite topics for the interview questions. Their structure is pretty simple, but they provide a basis for a wide range of different problems, from simple implementation to hard puzzles.
Balanced binary search trees (a variation of binary trees) appear in many areas of computer science. You also may get asked problems involving them, however, you are not expected to know how to code a self-balancing binary search tree in the interview. Still, given how ubiquitous and applicable they are in the real-life applications, you may want to read a bit more about them, for example in the Introduction to Algorithms book.
Let's solve a problem with binary tree to get some practice with them:
The following problem is a bit harder, and is also a nice exercise to think about binary trees:
There are three popular binary tree traversals: preorder, inorder, and postorder. Solve the following problems to learn more about them. For now, recursive solutions are fine.
Binary search trees is an important type of the binary trees. Try solving the following problem to learn more about them:
The following problems actively uses binary search tree structure to solve the task:
Let's do something more involved with binary search tree: delete a node with a specific value from it.
Sometimes when solving binary tree problems, you need to receive and somehow use some information from children. Let's see some problems to practice this:
Sometimes, binary tree problems are made a bit harder by asking you not to use the recursion. Let's see some examples. Solve the following problems without recursion now:
Sometimes solving binary tree problems requires some creative thinking. Try to solve the following problems:
Here are some more good binary tree problems to practice:
- 102. Binary Tree Level Order Traversal
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 108. Convert Sorted Array to Binary Search Tree
- 111. Minimum Depth of Binary Tree
- 199. Binary Tree Right Side View
- 235. Lowest Common Ancestor of a Binary Search Tree
- 543. Diameter of Binary Tree
- 617. Merge Two Binary Trees