Chapter 9: Tree Algorithm from Elements of Programming Interviews

is Tree balanaced
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;

if (getHeight(root) == -1)
return false;

return true;
}

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

int left = getHeight(root.left);
int right = getHeight(root.right);

if (left == -1 || right == -1)
return -1;

if (Math.abs(left - right) > 1) {
return -1;
}

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

}
  private static <T> int getHeight(BinaryTree<T> n) {
    if (n == null) {
      return -1;
    }

    int lHeight = getHeight(n.getLeft());
    if (lHeight == -2) {
      return -2; // left subtree is not balanced.
    }

    int rHeight = getHeight(n.getRight());
    if (rHeight == -2) {
      return -2; // right subtree is not balanced.
    }

    if (Math.abs(lHeight - rHeight) > 1) {
      return -2; // current node n is not balanced.
    }
    return Math.max(lHeight, rHeight) + 1;
  }


KBalancedBinaryTree - todo - return node which is not k blanaced but all descendent is k balanced
  private static <T> Pair<BinaryTree<T>, Integer> findNonKBalancedNodeHelper(
      BinaryTree<T> n, int k) {
    // Empty tree.
    if (n == null) {
      return new Pair<BinaryTree<T>, Integer>(null, 0);
    }

    // Early return if left subtree is not k-balanced.
    Pair<BinaryTree<T>, Integer> L = findNonKBalancedNodeHelper(n.getLeft(), k);
    if (L.getFirst() != null) {
      return L;
    }
    // Early return if right subtree is not k-balanced.
    Pair<BinaryTree<T>, Integer> R = findNonKBalancedNodeHelper(n.getRight(), k);
    if (R.getFirst() != null) {
      return R;
    }

    int nodeNum = L.getSecond() + R.getSecond() + 1; // # of nodes in n.
    if (Math.abs(L.getSecond() - R.getSecond()) > k) {
      return new Pair<BinaryTree<T>, Integer>(n, nodeNum);
    }
    return new Pair<BinaryTree<T>, Integer>(null, nodeNum);
  }
Symmetric Binary Tree
  private static <T> boolean isSymmetricHelper(BinaryTree<T> l, BinaryTree<T> r) {
    if (l == null && r == null) {
      return true;
    } else if (l != null && r != null) {
      return equals(l.getData(), r.getData())
          && isSymmetricHelper(l.getLeft(), r.getRight())
          && isSymmetricHelper(l.getRight(), r.getLeft());
    } else { // (l != null && r == null) || (l == null && r != null)
      return false;
    }
  }

Binary Tree Lock
  // @include
  public static class BinaryTree<T> {
    private BinaryTree<T> left, right, parent;
    private boolean locked;
    private int numChildrenLocks;

    public boolean isLock() {
      return locked;
    }

    public void lock() {
      if (numChildrenLocks == 0 && !locked) {
        // Make sure all parents do not lock.
        BinaryTree<T> n = parent;
        while (n != null) {
          if (n.locked) {
            return;
          }
          n = n.parent;
        }

        // Lock itself and update its parents.
        locked = true;
        n = parent;
        while (n != null) {
          ++n.numChildrenLocks;
          n = n.parent;
        }
      }
    }

    public void unlock() {
      if (locked) {
        // Unlock itself and update its parents.
        locked = false;
        BinaryTree<T> n = parent;
        while (n != null) {
          --n.numChildrenLocks;
          n = n.parent;
        }
      }
    }

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);
  }