Tree

HackerRank

If tree has N nodes => it has N-1 edges.

Binary Search Tree

Duplicate values does not make sense.

Left node < Parent Node < Right node (all right nodes)

Balanced vs Unbalanced tree

Unbalanced tree	Balanced tree
insert O(N)	insert O(logN)
find O(N)	find O(logN)

Definitions of Balanced tree

1

BST is balanced when the heights of the left and right subtrees of any node differ by at most one.

Traversing

Inorder traversing is useful for printing because you get elements in order.

DFS (Depth first search)

Inorder Traversal

Inorder traversal is a process for visiting each node in a binary tree by first visiting the left subtree, then the node itself, and then the right subtree. With inorder traversal, the path always favors the leftmost tree before traversing the rest.

The sequence produced with inorder traversal: 1, 3, 4, 6, 7, 8, 10, 13, 14.

In a binary search tree, inorder traversal results in visiting the nodes in ascending order. This is because by favoring resolving the left subtree at each node, at each node we are always moving toward the smallest value available and returning the inorder successor.

Implementation of Inorder DFS

Recursive solution

void inorderTraversal(BinaryTreeNode node) {
        // base case: if node is null, do nothing
        
        if (node != null) {
            // recurse on left child
            inorderTraversal(node.left);
            
            // visit current node
            System.out.print(node.data + " ");
            
            // recurse on right child
            inorderTraversal(node.right);
        }
}

Using stack

// https://www.youtube.com/watch?v=MZ67ceIH8v4
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        addLeftToStack(stack, root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(curr.val);
            if (curr.right != null) {
                addLeftToStack(stack, curr.right);
            }
        }
        return list;
    }

    private void addLeftToStack(Stack<TreeNode> stack, TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

Preorder Traversal

Preorder traversal visits each node in the tree by first visiting the node itself, then traversing the left subtree, and finally traversing the right subtree. In each recursive call, the function first prints (or "visits") the current node, then calls the recursive function on the left subtree, and finally on the right subtree.

binary search tree consisting of nine nodes and a height of four, with labels indicating the traversal order for preorder traversal.

The sequence produced with preorder traversal: 8, 3, 1, 6, 4, 7, 10, 14, 13

Preorder implementation

void preorderTraversal(BinaryTreeNode node) {
        // base case: if node is null, do nothing
        if (node != null) {
	    // visit current node
            System.out.print(node.data + " ");

            // recurse on left child
            preorderTraversal(node.left);
            
            // recurse on right child
            preorderTraversal(node.right);
        }
}

Postorder Traversal

In each recursive call, the function first performs DFS on the left subtree, then performs DFS on the right subtree, and finally visits the current node.

Postorder implementation

void postorderTraversal(BinaryTreeNode node) {
        // base case: if node is null, do nothing
        if (node != null) {
            // recurse on left child
            postorderTraversal(node.left);
            
            // recurse on right child
            postorderTraversal(node.right);

	   // visit current node
            System.out.print(node.data + " ");
        }
}

Postorder traversal is often used to delete the nodes of a tree in a specific order, because we can easily reconstruct the node references. We are basically marking the exact path of the recursive calls by immediately printing each node as it is visited.

BFS (Breadth first search)

Level Order Traversal

As an alternative to using DFS we can also traverse a binary tree using Breadth-First Search (BFS), where we visit each node belonging to the same level before moving deeper into the tree. BFS uses a queue data structure (instead of a stack or recursion), in order to maintain the level-order traversal.

binary search tree consisting of nine nodes and a height of four, with labels indicating the traversal order for level-order traversal.

The sequence produced with level order traversal: 8, 3, 10, 1, 6, 14, 4, 7, 13

Level order traversal in a binary tree is often applied to problems where we need to process tree nodes by level, or if we want to find the shortest distance between two nodes.

BFS implementation

public static void levelOrderTraversal(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");

        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Binary tree vs Binary Search tree

JAVA BST implementation

A binary search tree is a recursive data structure where each node can have 2 children at most.

BST Implementation

public class BinarySearchTree {
	Node root;
	
	// ADD
	public void add(int value) {
		root = addRecursive(root, value);
	}
	private Node addRecursive(Node current, int value) {
		if (current == null) {
			return new Node(value);
		}
		if (value < current.value) {
			current.left = addRecursive(current.left, value);
		} else if (value > current.value) {
			current.right = addRecursive(current.right, value);
		}
		return current;
	}
	
	// CONTAINS
	public boolean containsNode(int value) {
		return containsNodeRecursive(root, value);
	}
	private boolean containsNodeRecursive(Node current, int value) {
		if (current == null) {
			return false;
		}
		if (value == current.value) {
			return true;
		}
		return value < current.value
				? containsNodeRecursive(current.left, value)
				: containsNodeRecursive(current.right, value);
	}
		
	// TRAVERSE INORDER	
	public void traverseInOrder(Node node) {
		if (node != null) {
			traverseInOrder(node.left);
			visit(node.value);
			traverseInOrder(node.right);
		}
	}
	
	class Node {
		int value;
		Node left;
		Node right;
		
		Node(int value) {
			this.value = value;
			right = null;
			left = null;
		}
	}
}

Gist with full BinarySearchTree implementation.

Set of interview questions for BST

• Link 1 with answers (more implementation questions)

• Link 2 with answers

BST height

public static int height(Node root) {
		if (root == null) return -1;
		return Math.max(height(root.left), 
				height(root.right))+1;
	}

Related tasks

Is valid BST

/**
 * https://www.byte-by-byte.com/binarysearchtree/
 *
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode n, long min, long max) {
        if (n == null) return true;
        if (n.val <= min || n.val >= max) return false;
        return isValidBST(n.left, min, n.val) && isValidBST(n.right, n.val, max);
    }
}

Revert BST

// https://leetcode.com/problems/invert-binary-tree/
public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

Max depth of DST

max depth for this case is 3

Recursion solution

public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

BFS solution

public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int level = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.remove();
                if (curr.left != null) queue.add(curr.left);
                if (curr.right != null) queue.add(curr.right);
            }
            level++;
        }
        return level;
    }

N-ary Trees

N-ary trees are simply the generalized form of a tree. Rather than a binary tree where each node is limited to having at most two children, an n-ary tree can have any number of children.

However, this still requires our graph to be directional and acyclic and for each node to only have one parent.

Here’s an example of what one of these n-ary trees might look like:

n-ary tree

Notice how the 1 node has more than 2 children. N-ary trees allow us to generalize our trees and do things like we’ll see in the next structure.

Trie

Explanation

Tries are n-ary trees that are specifically used to store string data. Tries are designed to store multiple strings as efficiently as possible by merging the prefixes that are common across multiple strings.

These are becoming more popular in interviews because they do a great job of testing that you understand trees beyond the most basic level.

Here’s an example of what a trie might look like:

trie

Notice how all strings with the same prefix are merged into the same subtree.

I’m not going to go into a lot of detail on tries here, but I recommend this post for a more in depth discussion.

When to Use Binary Trees In Technical Interviews

Most of the time, interview questions involving trees will be explicitly stated as such. The problem will come in the form of “Given a tree, do X”. Sometimes, the task may be challenging but not very ambiguous, for example validating a binary search tree. The most important thing when you see problems like this is to make sure that you understand what type of tree you’re dealing with. If it’s a BST, that has different implications than a binary tree that is not sorted, and could provide valuable clues for arriving at an optimal solution.

In other cases, we might be asked to store data efficiently - this could be an opportunity to implement a BST. A common interview task is to implement the insertion and search functions of a BST, as this is a great way to demonstrate one's understanding of the data structure, so be sure to practice these. Deleting a node from a BST can be asked as well but is often considered an advanced topic.

For generic binary trees, questions often involve assessing the dimensions of the tree, for example the height or diameter of the tree, or searching specific conditions between two or more nodes in the tree, like LCA or path sum. Here are some areas that come up often in interviews:

1. Height: Calculate the height of a binary tree (the number of edges on the longest path from the root to a leaf node).

2. Find Mirror Image: Determine if a binary tree is a mirror image of itself (symmetric).

3. Lowest Common Ancestor (LCA): Given two nodes in a binary tree, find their lowest common ancestor node.

4. Diameter of a Tree: Calculate the diameter of a binary tree (the length of the longest path between any two nodes).

5. Path Sum: Check if there exists a root-to-leaf path in a binary tree that adds up to a given sum. 6.Serialize and Deserialize: Serialize a binary tree into a string representation and deserialize it back to a binary tree.

Common Mistakes in Interviews Featuring Binary Trees

• Mistaking a Binary Tree for a Binary Search Tree. Remember that an interviewer might intentionally leave information out of their problem description to leave room for your inquiries. The difference between a general binary tree and a BST will greatly influence the solution you propose.

• Forgetting to consider duplicate keys when implementing a BST. Paying close attention to implementation details will help demonstrate your familiarity with the data structure.

• Not using visual aids. Binary tree logic can become very complex, given its recursive nature. Using tree diagrams can help you work through the problem and communicate more effectively with your interviewer.

• Misusing BFS or DFS. In some binary tree problems, where we don't have a sorted tree or we simply need to visit every node to perform some operation, both traversal algorithms are applicable without any meaningful complexity tradeoff. But a candidate needs to be confident about which situations call for a specific traversal. A common use-case for BFS, for example, is searching for the shortest path between two nodes. DFS on the other hand, is useful to perform on a binary search tree when we want to traverse the nodes in their sorted order.

• Forgetting to set min/max bounds when validating binary search trees. An incorrect implementation just checks whether node.right.data > node.left.data and node.left.data < node.right.data

• Not knowing how to use recursion within trees. Trees are inherently recursive data structures, so it's important to be familiar with recursive traversal. It may be obvious how to traverse from parent to child, but using recursive to traverse from child to parent (with return statement) is essential.

• Incorrectly stating space complexity for recursive traversal. It is easy to forget that recursion doesn't use additional space since we are not introducing a new data structure. But in fact, we are taking advantage of an existing stack call the call stack, which must grow linearly with the number of nodes we are recursing on.

• Forgetting to handle edge cases. Binary tree nodes can still have zero or one child, so be sure to explicitly check for edge cases. We also need to include base cases for recursive traversals.

Clarifying Questions to Ask Your Interviewer About Binary Trees

• Is the input binary tree or a binary search tree? Clarifying the parameters offered by the interviewer is a great problem-solving skill to demonstrate. In some cases, interviewers will intentionally omit that the binary tree you're working with is actually sorted, so be sure to ask! This of course will have a huge impact on the approach you'll end up taking for your solution.

• Will the input contain duplicate values? Whether you are streaming values or getting a tree as input, make sure to specify if duplicates need to be handled, as this complicates binary search tree implementation. For binary search trees, this is especially complicated, and will likely be the crux of the problem if the tree contains them. Alternatively, you might be building a BST from a stream of values, and you'll want to be sure you can omit duplicates if its appropriate in the problem.

• How do we handle scenarios where a binary tree is empty or has null nodes? It is always encouraged to ask about how edge cases should be handled, as some interviewers will be happy enough that you communicated that you are aware of them, and will offer to let you skip implementation.

• What operations need to be supported? If you'll be implementing a binary tree, make sure to ask your interviewer what operations to prioritize during the interview. In some cases, they can allow you to skip the implementation of some less-important operations.

• What are the characteristics of the input tree? Be sure to determine if there are any constraints that the input binary tree adheres to, such as balancing or sorting, max height, weighted branches, etc. If so, this would be a clue as to what kind of tree data structure you should focus on during the interview.

How to Show Mastery of Trees in Interviews

Know Your BST

One of the most common topics in software engineering interviews is the Binary Search Tree. You want to be able to showcase your ability to implement binary trees efficiently and correctly. Make sure to practice implementing tree construction, node insertion, deletion, and traversal algorithms.

Speaking of traversal algorithms - many interview problems test your understanding of the traversal order, especially when working with binary search trees, since the output sequence order is not arbitrary. Be sure to understand the use-cases for preorder, inorder, postorder, and level-order traversals.

Be Familiar with Recursive and Iterative Implementations of DFS

Although trees are inherently recursive, and thus lend themselves to recursive traversal implementations, a candidate should be comfortable with the iterative implementation as well. This helps demonstrate your strong understanding of recursion as well, since we can mimic the recursive mechanism we get from the call stack with a stack we implement ourselves. The above traversals are all recursive - here's an example of an iterative DFS: