Solving Tree-related Problems

  • Binary Tree: a tree in which each node has up to two children
  • Binary Search Tree: a binary tree in which every node fits a specific ordering property: all left descendants ≤ n < all right descendants.

Complete Traversal

  • Given a binary tree, determine if it is height-balanced.
  • Given a binary tree, find its maximum depth.
  • Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
  • Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
  • Invert a binary tree.
  • Flatten Binary Tree to Linked List
  • Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

Partial Traversal

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
int min = Math.min(p.val, q.val);
int max = Math.max(p.val, q.val);

if (root.val >= min && root.val <= max) {
return root;
}

return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return getHeight(root.left) + 1;
}
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}

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

// this means we can take the whole left subtree and the root
// we recursively need to countNodes(root.right);
if (lh == rh) {
return (1 << lh) + countNodes(root.right);
}

// otherwise, it means we can take right subtree and the root
// we resursively need to countNodes(root.left);
return (1 << rh) + countNodes(root.left);
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store