Tree Examples

Here are some resources to learn about trees:

Try to do each example yourself first.

Sum Path

(Question from InterviewBit)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example :

Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Solution

We need a tree traversal that will explore every root-to-leaf path and keep track of the sum so far along the way: depth first search. When we get to a leaf, check that the current sum is equal to the target, if so return true. Otherwise, return false. Each non-leaf node in the DFS returns true if at least one of its children has a valid root-to-leaf path sum and false otherwise. Think of this as passing a valid solution up the tree to the root when DFS backtracks.

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
  public int hasPathSum(TreeNode node, int target) {
    return hasPathSum(node, target, 0) ? 1 : 0;
  }

  public boolean hasPathSum(TreeNode node, int target, int current) {
    if (node == null) {
      return false;
    }
    if (node.left == null && node.right == null) {
      return target == current + node.val;
    }
    return hasPathSum(node.left, target, current + node.val) ||
        hasPathSum(node.right, target, current + node.val);
  }
}

What is the time complexity? Notice that there are two recursive calls to the left and right subtrees. This is just a tree traversal so we visit each node exactly once so the complexity is in the number nodes.

Minimum Depth

(Question from InterviewBit)

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

NOTE : The path has to end on a leaf node. Example :

     1
    /
   2

min depth = 2.

Solution

Notice that when we do a DFS traversal through the tree, every visit to a child increases the depth to the root by 1. Let's keep track of this number. When we reach a leaf, we pass this number to its parent. The parent takes the minimum depth passed back by its children and passes this to its parent and so on.

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
  public int minDepth(TreeNode root) {
    return minDepth(root, 1);
  }

  public int minDepth(TreeNode node, int depth) {
    if (node.left == null && node.right == null) {
      return depth;
    }
    int result = Integer.MAX_VALUE;
    if (node.left != null) {
      result = Math.min(result, minDepth(node.left, depth + 1));
    }
    if (node.right != null) {
      result = Math.min(result, minDepth(node.right, depth + 1));
    }
    return result;
  }
}

What is the time complexity? Notice that there are at most two recursive calls to the left and right subtrees. This is just a tree traversal so we visit each node exactly once so the complexity is in the number nodes.

Invert Binary Tree

(Question from InterviewBit)

Given a binary tree, invert the binary tree and return it. Look at the example for more details.

Example : Given binary tree

     1
   /   \
  2     3
 / \   / \
4   5 6   7

invert and return


     1
   /   \
  3     2
 / \   / \
7   6 5   4

Solution

Use the base case and build approach (AKA inductive reasoning). How do you invert a tree of height 1? You swap the left and right subtrees. How do you invert a tree of height 2? Well, you know that the left and right subtrees are of height 1 and you already know how to invert that. Thus, invert the left and right subtrees and then swap their pointers.

This solution is most easily solved using recursion. The base case of our recursion is when we have a leaf node. In this case we do nothing. Otherwise, we swap the left and right pointers.

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
  public TreeNode invertTree(TreeNode root) {
    if (root == null) {
      return null;
    }

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

    // Swap the left and right children.
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    return root;
  }
}

What is the time complexity? Notice that there are two recursive calls to the left and right then we swap the pointers. This is a post order traversal so we visit each node exactly once so the complexity is in the number nodes.

More Examples

Graph Examples

Here are some resources to learn about graphs:

Try to do each example yourself first.

Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  • Only one letter can be changed at a time
  • Each intermediate word must exist in the word list

For example, given:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution

We can represent this problem as a graph where each node is a word and two nodes are connected if they differ by one letter. Given a dictionary, we can construct this graph in time ( is the number of words in the dictionary and is the number of letters in each word) using something like this:

for (String s : dictionary) { // n iterations
  for (String t : dictionary) { // n iterations
    if (!s.equals(t) && differsByOneLetter(s, t)) { // O(m)
      graph.addEdge(s, t);
    }
  }
}

Now that our graph is constructed, how do we find the shortest distance between beginWord and endWord? Because the graph is unweighted, we can find the shortest path using a breadth-first search in time. ( is the number of edges)

This solution runs in but we can do better. Can you think of a faster solution?

Optimal Solution

The graph building is our bottleneck so we should try to reduce its time complexity. Notice we are building edges in our graph that may not be used in the path from beginWord to endWord. Instead of building a graph, let's do a modified BFS where we only traverse edges when we need them. Using a BFS, each node is processed at most once.

For each node, we find its neighbours by varying each letter in the current word and check if it exists in the dictionary. If it does, then there is an edge to that word and we enqueue it to be searched later.

What is the time complexity? Every time we visit a node, we must do contains operations on our dictionary, each taking . In the worst case, we visit every node so the time complexity is .

public int ladderLength(String beginWord, String endWord, Set<String> wordSet) {
  // Stores the distances.
  Map<String, Integer> dist = new HashMap<>();
  Queue<String> queue = new ArrayDeque<>();

  queue.add(beginWord);
  dist.put(beginWord, 1);

  while (!queue.isEmpty()) {
    String current = queue.remove();
    int d = dist.get(current);
    char[] s = current.toCharArray();
    for (int i = 0; i < s.length; i++) {
      char save = s[i];
      for (char c = 'a'; c <= 'z'; c++) {
        if (c == save) {
          continue;
        }
        s[i] = c;
        String t = new String(s);
        // If we are at an intermediate word, and we can reach endWord.
        if (d > 0 && t.equals(endWord)) {
          return d + 1;
        }
        if (wordSet.contains(t) && !dist.containsKey(t)) {
          queue.add(t);
          dist.put(t, d + 1);
        }
      }
      s[i] = save;
    }
  }
  return 0;
}

More Examples

Advanced

results matching ""

    No results matching ""