Trees Interview Questions

Trees are a data structure that models a hierarchical collection of nodes via links. We'll tackle some problems in this section to get practice in.

In the majority of cases, we've given you some environment variables that provide the object structure of a tree, letting you focus on the algorithm at hand!

Section Menu

How do I use this section?

1. CHALLENGE

Binary Tree Inorder Traversal

Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes? 4 \ 5 / 6 The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order before 5. <img src="https://storage.googleapis.com/algodailyrandomassets/cu...

2. CHALLENGE

Mean Per Level

We are given a binary tree and are tasked with writing a method that determines the average of every level in the tree. So for instance, given the following binary tree, we'd get [2, 5, 7] if the method grabbed the correct means. <img src="https://storage.googleapis.com/a...

3. CHALLENGE

Identical Trees

Can you write a function to see if two binary trees are identical? ` 1 1 / \ / \ 2 3 2 3 ` The above two trees share the same structure in terms of shape and location of each parent nodes' children. <img src="https://storage.googleapis.com/algodailyrandomassets/challenges/bstremoveleaf...

4. CHALLENGE

String From Binary Tree

Suppose we're given a simple binary tree like the following: 1 / \ 2 3 \ 4 Can you generate a string based off the values of its nodes? <img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/str...

5. CHALLENGE

Implement a Binary Search Tree

Let's implement a Binary Search Tree! Recall that a binary search tree, or a BST, is a binary tree that is ordered via these two properties: The left sub-tree of a node has a value less than or equal to its parent node's value. The right sub-tree of a node has a v...

6. CHALLENGE

How Deep Does It Go? Maximum Depth of Binary tree

Write a method to determine how deep a binary tree goes. The tree's depth can be described as the number of nodes you encounter as you traverse from the root node to a leaf. The root node is the topmost node, and a leaf is a node with no children. For example,...

7. CHALLENGE

Implement the Trie Data Structure

Suppose you're asked during an interview to design an autocompletion system. On the client side, you have an input box. When users start typing things into the input, it should parse what's been typed and ma...

8. CHALLENGE

Sum Right Side Leaves

Finding the Sum of Right Leaves in a Binary Tree Imagine a family tree, but instead of tracking your relatives, it's tracking numbers. Each "person" in this tree has at most two "children," and some have none. We call these childless nodes "leaves," and your task is to find the sum of leaves that are on the right side of their...

9. CHALLENGE

Invert a Binary Tree

Can you invert a binary tree over its vertical axis? This is a famous problem made popular by this tweet: Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f**k off.&mdash; Max Howell (@mxcl) <a href="https://twitter.co...

10. CHALLENGE

Serialize and Deserialize a Binary Tree

Given a binary tree representation, can you come up with a method to serialize the tree and then deserialize it to get the exact same tree? What is Serialization and Deserialization? Serializat...

11. CHALLENGE

Get Binary Tree Leaves

Suppose we're given a binary tree, one with several leaves like such: We're asked to get all the current leaf values, then delete the leaves. Then we repeat-- we again get the leaf values, and then delete-- proceeding un...

12. CHALLENGE

Diameter of Binary Tree

Diameter of Binary Tree Let's find out the length of the diameter of the tree! This is a simple binary tree question that is frequently asked in interviews. So let's see how we can solve this problem. Prompt Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a bina...

13. CHALLENGE

Right Node View of Binary Tree

A binary search tree is a data structure that has the following properties, Each node in the tree has only two children. The left subtree consists of nodes with values less than the root node. The right subtree consists of nodes with values greater than the root node. Consider a binary tree with the root node given as `roo...

14. CHALLENGE

Nodes in Binary Tree Columns

Vertical Order Traversal of a Binary Tree What is Vertical Order Traversal? In a binary tree, each node has a position defined by its (row, col) coordinates. The vertical order traversal is a method of visiting all the nodes in the tree column-by-column, starting from the leftmost to the rightmost columns. In this travers...