Trees Interview Questions & Tips

By Kenny Polyak | Last updated: June 18, 2024

What is a Tree?

A tree is a hierarchical data structure in computer science consisting of nodes connected by edges. Each node is an element which can store data, representing some scalar value or a key, and the edges contained in that node, representing references to other nodes.

In the most general sense, trees are simply directed acyclic graphs (DAGs) where each node can only have a single other node pointing to it, containing N nodes and N-1 edges. As a hierarchical structure, the topmost node in a tree is called the root node, which has no parent. Every other node in the tree has exactly one parent node and contains connections to an arbitrary number of child nodes; a node that has no children is called a leaf node.

Node Structure

There is no superstructure that can randomly access any particular node in the tree. Instead, trees are inherently recursive: each child of a node is a subtree in itself. When handling trees in software engineering, we usually pass around a reference to the root, from which we can access and manipulate the tree data.

Here's an example of tree node definition:

Java

class TreeNode {
    Integer data = null;
    List<TreeNode> children = new ArrayList<TreeNode>();

TreeNode(Integer value) {
        data = value;
    }
}

Typically, children don't have references to their parents. While this is a possible modification to make on the tree node if the need justifies the extra space, it is rarely done given that the tree is almost always traversed from the root. To learn more about graph and tree traversal algorithms, read about Depth-First Search and Breadth-First Search.

Different Types of Trees

Trees can be tall or wide and everything in between. Since the only restriction on a tree is that the edges are directed and there are no cycles, we can find really tall trees where each node only has one child, or really wide trees where each node has thousands of children.

Trees can have rulesets that enforce the order of nodes on insertion, or they can be randomly built top-down.

By applying specific rulesets to trees, we can define different subtypes with their own advantages and tradeoffs. Typically, these subtypes enforce some criteria related to the height of the tree - the height of a tree is the number of edges in the longest path from the root to a leaf - or to the order that tree nodes must be in.

There are many types of tree implementations, each with their own set of rules and advantages. Below are a just a few examples, with links to further discussion for the tree types we see most often in interviews:

• Binary Trees: a tree where each node has up to two children.
• N-ary Trees: a tree where each node can have any number of children.
• Binary Search Trees: a binary tree where each node value follows a specific ordering property - the node is greater than all the nodes in its left subtree and smaller than all the nodes in its right subtree.
• AVL and Red-black Trees: a height-balanced tree, such that the heights of the left and right subtrees do not differ more than a certain amount.
• Binary Heap Trees: a complete binary tree that satisfies the heap property, used for priority queue operations.
• Tries: an n-ary tree specifically used to store string data.

Common Operations on Trees

Although the implementation of these operations will differ greatly based on the type of tree, let's look at the simplest case with an unbalanced N-ary tree - this is a tree without any constraints on the positions of nodes or the number of children per node.

Insert

If there are no constraints on where a node needs to be in a tree, then insertion can be as simple as finding a leaf and adding it as a new child. Below we implement a version of insert where we add the new node as a child to a specific parent.

Java

public static void insertNode(TreeNode root, Integer parentValue, Integer newValue) {
  if (root == null) return;
  if (root.val == parentValue) {
    TreeNode newNode = new TreeNode(newValue);
    root.children.add(newNode);
    return;
  }
  for (TreeNode child: root.children) {
    insertNode(child, parentValue, newValue);
  }
}

Basic Search

Searching in a tree is often explored in terms of traversal algorithms, as these will determine the path taken to search. But in its simplest form, searching in a tree is merely a recursive function - taking advantage of the recursive nature of a tree - that calls itself on each child of a node until the target node is found.

Java

 public static TreeNode searchNode(TreeNode root, Integer target) {
        if (root == null || root.val == target) {
            return root;
        }
        for (TreeNode child : root.children) {
            TreeNode result = searchNode(child, target);
            if (result != null) {
                return result;
            }
        }
        return null;
    }

Delete

Deleting nodes from a tree is sometimes considered an advanced topic, especially when we want to preserve subtrees or adhere to constraints on the tree structure itself. We won't be diving into those here. But, if we want to delete an entire subtree, it's as easy as performing the searchNode method above, and once the target is identified, removing it from the list of children from its parent.

When to Use Trees In Technical Interviews

Trees come up often in technical interview questions because they’re the right amount of difficulty to challenge candidates without taking an unreasonable amount of time for those who understand them. As a result, trees come up in both coding and system design interviews.

Using Trees in Coding Interviews

The most common tree questions involve either manipulation or traversal of trees. Manipulation can look like building a tree, converting a tree from one format to another, converting a linked list to a tree, inserting/removing nodes from a tree, and the like. These really test that you thoroughly understand how the data is structured.

Tree traversals generally involve iterating over the tree or searching for data in the tree. This is where we will use tools like depth-first search (DFS) and breadth-first search (BFS) to our advantage.

Most tree interview problems will explicitly have a tree data structure as an input. These are usually cases where we'll be asked to traverse the tree, but it's also important to be familiar with adding and deleting nodes from a tree.

Common Trees interview Questions

• The Lowest Common Ancestor (LCA) problem: Given two nodes in a binary tree, find their lowest common ancestor node.
• Checking if a tree is a subtree of another tree: this requires being able to write an algorithm that traverses the tree and can identify duplicate sub-structures.
• Maximum Path Sum: Find the maximum sum of values along any path from the root to a leaf node in a tree.
• Find the Height of a Tree: Calculate the height of a tree (the number of edges on the longest path from the root to a leaf node).

Finally, there are problems where the use of a tree is not so obvious. One common example is using a trie to find string prefixes. If a problem asks us to find strings by their prefix, for example when looking up a term in a dictionary or when implementing an autocomplete tool, then tries are inherently a great way to do that.

Using Trees in System Design Interviews

Here are some examples of where trees are commonly used:

1. File Systems: Many file systems, such as the hierarchical file systems used in operating systems, utilize tree structures. Directories and subdirectories can be represented as nodes in a tree.
2. Search Engines: Search engines use tree-based indexing structures like tries to efficiently store and retrieve data related to keywords or phrases.
3. User Interfaces: Tree structures are used in various user interface components, such as menus, navigation bars, and organization charts. They enable hierarchical representation and navigation of elements.
4. Compilers: Control flow graphs (CFGs) and other tree-based structures are used in compiler optimizations to analyze program flow and optimize code generation. Trees can also be used to map dependencies.
5. XML/HTML Parsing: Tree structures are used in parsing and representing XML and HTML documents. The Document Object Model (DOM) represents these documents as trees, allowing for efficient manipulation and traversal.

Common Mistakes in Interviews Featuring Trees

• Forgetting to handle edge cases. When implementing an algorithm involving a tree, be sure to explicitly check cases where the tree has none or only one node. This is often missed when working through solutions. Given that trees are often used in recursive algorithms, we also typically need to include base cases.
• Mishandling leaf nodes. All trees with nodes have leaves, and it’s easy for our logic to unintentionally try to access the children of a leaf, which could lead to a null pointer exception.
• Not using a diagram to problem-solve and communicate. Tree logic can become very complex, given its recursive nature. Make sure to visualize your algorithm with a tree diagram before you start coding, and focus on simple and readable code.
• Not considering tradeoffs in time and space complexity. Since we can customize tree nodes to fit our use cases, be sure to discuss the space implications of your solutions with your interviewer.
• Misunderstanding tree terminology. Make sure to correctly understand and use terms such as root, parent, child, leaf, subtree, depth, and height. For example, interview questions often ask us to find the depth or height of a tree, or count the leaves of a tree - it's important to be familiar with these concepts.
• Misusing BFS or DFS. Although there are cases where both traversal algorithms are applicable without any meaningful complexity tradeoff, candidates need to be confident about which situations call for a specific traversal.

Clarifying Questions to Ask Your Interviewer About Trees

1. Can we prioritize time complexity over space? All data structures involve some kind of tradeoff, and trees are no different.
2. How frequently will tree operations be performed? Knowing if the problem will be more read or write heavy will help inform the approach.
3. What operations need to be supported? If you'll be implementing a tree, be sure to ask your interviewer what operations to prioritize during the interview.
4. What are the characteristics of the input tree? Be sure to determine if there are any constraints that the input tree adheres to, such as balancing or sorting.
5. Is the input tree an n-ary tree, a binary tree or a binary search tree? Be sure to ask your interviewer if the input tree is a specific type of tree.