Binary Trees

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.

Before we begin

Some graph and recursion knowledge would be very helpful in the binary tree questions. So, if you haven't already, first read the sections about graphs and recursion on this website.

Binary tree problems

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:

Binary tree traversals

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

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.

Receiving information from children

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:

Getting rid of the recursion

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:

Unusual binary tree problems

Sometimes solving binary tree problems requires some creative thinking. Try to solve the following problems:

Practice problems

Here are some more good binary tree problems to practice: