Chapter 9: Tree Algorithm from Elements of Programming Interviews

Inorder Traversal With Parent Node
  public static <T> void inOrderTraversal(BinaryTree<T> r) {
    // Empty tree.
    if (r == null) {
      return;
    }

    BinaryTree<T> prev = null, curr = r, next;
    while (curr != null) {
      if (prev == null || prev.getLeft() == curr || prev.getRight() == curr) {
        if (curr.getLeft() != null) {
          next = curr.getLeft();
        } else {
          System.out.println(curr.getData());
          next = (curr.getRight() != null ? curr.getRight() : curr.getParent());
        }
      } else if (curr.getLeft() == prev) {
        System.out.println(curr.getData());
        next = (curr.getRight() != null ? curr.getRight() : curr.getParent());
      } else {
        next = curr.getParent();
      }

      prev = curr;
      curr = next;
    }
  }

Find Kth node with size field
  public static <T> BinaryTree<T> findKthNodeBinaryTree(BinaryTree<T> root,
      int k) {
    BinaryTree<T> n = root;
    while (n != null) {
      int leftSize = n.getLeft() != null ? n.getLeft().getSize() : 0;
      if (leftSize < k - 1) {
        k -= (leftSize + 1);
        n = n.getRight();
      } else if (leftSize == k - 1) {
        return n;
      } else { // leftSize > k - 1.
        n = n.getLeft();
      }
    }
    throw new RuntimeException("no k-th node in binary tree");
  }

Reconstruct Binary Tree PreInOrders
  public static <T> BinaryTree<T> reconstructPreInOrders(ArrayList<T> pre,
      ArrayList<T> in) {
    return reconstructPreInOrdersHelper(pre, 0, pre.size(), in, 0, in.size());
  }
 
  private static <T> BinaryTree<T> reconstructPreInOrdersHelper(
      ArrayList<T> pre, int preS, int preE, ArrayList<T> in, int inS, int inE) {
    if (preE > preS && inE > inS) {
      int it = in.subList(inS, inE).indexOf(pre.get(preS));
      it = it < 0 ? inE : (it + inS);
      int leftTreeSize = it - inS;

      return new BinaryTree<T>(pre.get(preS), reconstructPreInOrdersHelper(pre,
          preS + 1, preS + 1 + leftTreeSize, in, inS, it),
          reconstructPreInOrdersHelper(pre, preS + 1 + leftTreeSize, preE, in,
              it + 1, inE));
    }
    return null;
  }

Reconstruct Binary Tree Post InOrders
  private static <T> BinaryTree<T> reconstructPostInOrdersHelper(
      ArrayList<T> post, int postS, int postE, ArrayList<T> in,
          int inS, int inE) {
    if (postE > postS && inE > inS) {
      int it = in.subList(inS, inE).indexOf(post.get(postE - 1));
      it = it < 0 ? inE : (it + inS);
      int leftTreeSize = it - inS;
      return new BinaryTree<T>(post.get(postE - 1),
      // Recursively build the left subtree.
          reconstructPostInOrdersHelper(post, postS, postS + leftTreeSize, in,
              inS, it),
          // Recursively build the right subtree.
          reconstructPostInOrdersHelper(post, postS + leftTreeSize, postE - 1,
              in, it + 1, inE));
    }
    return null;
  }

  public static <T> BinaryTree<T> reconstructPostInOrders(ArrayList<T> post,
      ArrayList<T> in) {
    return reconstructPostInOrdersHelper(post, 0, post.size(), in, 0, in.size());
  }

Reconstruct Preorder With Null for empty children
  public static <T> BinaryTree<T> reconstructPreorder(ArrayList<T> preorder) {
    LinkedList<BinaryTree<T>> s = new LinkedList<BinaryTree<T>>();
    for (int i = preorder.size() - 1; i >= 0; i--) {
      if (preorder.get(i) == null) {
        s.push(null);
      } else {
        BinaryTree<T> l = s.pop();
        BinaryTree<T> r = s.pop();
        s.push(new BinaryTree<T>(preorder.get(i), l, r));
      }
    }
    return s.peek();
  }
Connect Leaves Binary Tree
  private static <T> void connectLeavesHelper(BinaryTree<T> n,
      ArrayList<BinaryTree<T>> L) {
    if (n != null) {
      if (n.getLeft() == null && n.getRight() == null) {
        L.add(n);
      } else {
        connectLeavesHelper(n.getLeft(), L);
        connectLeavesHelper(n.getRight(), L);
      }
    }
  }

Exterior Binary Tree - todo
  private static <T> void leftBoundaryBTree(BinaryTree<T> n, boolean isBoundary) {
    if (n != null) {
      if (isBoundary || (n.getLeft() == null && n.getRight() == null)) {
        System.out.print(n.getData() + " ");
      }
      leftBoundaryBTree(n.getLeft(), isBoundary);
      leftBoundaryBTree(n.getRight(), isBoundary && n.getLeft() == null);
    }
  }

  private static <T> void rightBoundaryBTree(
      BinaryTree<T> n, boolean isBoundary) {
    if (n != null) {
      rightBoundaryBTree(n.getLeft(), isBoundary && n.getRight() == null);
      rightBoundaryBTree(n.getRight(), isBoundary);
      if (isBoundary || (n.getLeft() == null && n.getRight() == null)) {
        System.out.print(n.getData() + " ");
      }
    }
  }

  public static <T> void exteriorBinaryTree(BinaryTree<T> root) {
    if (root != null) {
      System.out.print(root.getData() + " ");
      leftBoundaryBTree(root.getLeft(), true);
      rightBoundaryBTree(root.getRight(), true);
    }
  }
 
Lowest common ancestor without parent node
  public static <T> BinaryTree<T> LCA(BinaryTree<T> n, BinaryTree<T> a,
      BinaryTree<T> b) {
    if (n == null) { // empty subtree.
      return null;
    } else if (n == a || n == b) {
      return n;
    }

    BinaryTree<T> lRes = LCA(n.getLeft(), a, b), rRes = LCA(n.getRight(), a, b);
    if (lRes != null && rRes != null) {
      return n;
    } else {
      return lRes != null ? lRes : rRes;
    }
  }

Lowest common ancestor with parent node
  private static <T> int getDepth(BinaryTree<T> n) {
    int d = 0;
    while (n != null) {
      ++d;
      n = n.getParent();
    }
    return d;
  }

  public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
    int depthI = getDepth(i), depthJ = getDepth(j);
    if (depthJ > depthI) {
      BinaryTree<T> temp = i;
      i = j;
      j = temp;
    }

    // Advance deeper node first.
    int depthDiff = Math.abs(depthI - depthJ);
    while (depthDiff-- > 0) {
      i = i.getParent();
    }

    // Both pointers advance until they found a common ancestor.
    while (i != j) {
      i = i.getParent();
      j = j.getParent();
    }
    return i;
  }

LowestCommonAncestorHash
  public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
    HashSet<BinaryTree<T>> hash = new HashSet<BinaryTree<T>>();
    while (i != null || j != null) {
      if (i != null) {
        if (hash.add(i) == false) {
          return i; // adds a failed because a exists in hash.
        }
        i = i.getParent();
      }
      if (j != null) {
        if (hash.add(j) == false) {
          return j; // adds a failed because a exists in hash.
        }
        j = j.getParent();
      }
    }
    // Throw error if a and b are not in the same tree.
    throw new RuntimeException("a and b are not in the same tree");
  }
Shortest Unique Prefix
    public String getShortestUniquePrefix(String s) {
      TrieNode p = root;
      StringBuilder prefix = new StringBuilder();
      for (char c : s.toCharArray()) {
        prefix.append(c);
        if (!p.getLeaves().containsKey(c)) {
          return prefix.toString();
        }
        p = p.getLeaves().get(c);
      }
      return "";
    }
  public static String findShortestPrefix(String s, HashSet<String> D) {
    // Build a trie according to given dictionary D.
    Trie T = new Trie();
    for (String word : D) {
      T.insert(word);
    }
    return T.getShortestUniquePrefix(s);
  }