Question

Formatted question description: https://leetcode.ca/all/236.html

 236. Lowest Common Ancestor of a Binary Tree

 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

 According to the definition of LCA on Wikipedia:
     “The lowest common ancestor is defined between two nodes v and w
     as the lowest node in T that has both v and w as descendants
     (where we allow a node to be a descendant of itself).”

          _______3______
         /              \
      ___5__          ___1__
     /      \        /      \
     6      _2      0        8
   /  \
  7   4

 For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3.
 Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

 @tag-tree

Algorithm

The very simple idea is to see where the two values are compared with root:

  • Both values are on the left, then LCA is on the left
  • Both values are on the right, then LCA is on the right
  • One on the left and one on the right means that LCA is the current root node.

Code

Java

import javafx.util.Pair;
import java.util.Stack;


public class Lowest_Common_Ancestor_of_a_Binary_Tree {

    public static void main(String[] args) {
        Lowest_Common_Ancestor_of_a_Binary_Tree out = new Lowest_Common_Ancestor_of_a_Binary_Tree();
        Solution s = out.new Solution();

        TreeNode root = new TreeNode(3);
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(1);

        root.left = p;
        root.right = q;

        System.out.println(s.lowestCommonAncestor(root, p, q).val);


        TreeNode root2 = new TreeNode(1);
        TreeNode p2 = new TreeNode(2);

        root2.left = p2;

        System.out.println(s.lowestCommonAncestor(root2, p2, root2).val);

    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

            if (root == null) {
                return null;
            }

            if (root == p || root == q) { // key is here, especially when p is parent of q or vice-versa
                return root;
            }

            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);

            if (left != null && right != null) {
                return root;
            } else if (left == null && right == null) {
                return null;
            } else if (left == null && right != null) {
                return right;
            } else { // left != null && right == null
                return left;
            }
        }
    }

    class Solution_iteration {

        // Three static flags to keep track of post-order traversal.

        // Both left and right traversal pending for a node.
        // Indicates the nodes children are yet to be traversed.
        private int BOTH_PENDING = 2;

        // Left traversal done.
        private int LEFT_DONE = 1;

        // Both left and right traversal done for a node.
        // Indicates the node can be popped off the stack.
        private int BOTH_DONE = 0;

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

            Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();

            // Initialize the stack with the root node.
            stack.push(new Pair<TreeNode, Integer>(root, this.BOTH_PENDING));

            // This flag is set when either one of p or q is found.
            boolean one_node_found = false;

            // This is used to keep track of the LCA.
            TreeNode LCA = null;

            // Child node
            TreeNode child_node = null;

            // We do a post order traversal of the binary tree using stack
            while (!stack.isEmpty()) {

                Pair<TreeNode, Integer> top = stack.peek();
                TreeNode parent_node = top.getKey();
                int parent_state = top.getValue();

                // If the parent_state is not equal to BOTH_DONE,
                // this means the parent_node can't be popped off yet.
                if (parent_state != this.BOTH_DONE) {

                    // If both child traversals are pending
                    if (parent_state == this.BOTH_PENDING) {

                        // Check if the current parent_node is either p or q.
                        if (parent_node == p || parent_node == q) {

                            // If one_node_found was set already, this means we have found
                            // both the nodes.
                            if (one_node_found) {
                                return LCA;
                            } else {
                                // Otherwise, set one_node_found to True,
                                // to mark one of p and q is found.
                                one_node_found = true;

                                // Save the current top element of stack as the LCA.
                                LCA = stack.peek().getKey();
                            }
                        }

                        // If both pending, traverse the left child first
                        child_node = parent_node.left;
                    } else {
                        // traverse right child
                        child_node = parent_node.right;
                    }

                    // Update the node state at the top of the stack
                    // Since we have visited one more child.
                    stack.pop();
                    stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1));

                    // Add the child node to the stack for traversal.
                    if (child_node != null) {
                        stack.push(new Pair<TreeNode, Integer>(child_node, this.BOTH_PENDING));
                    }
                } else {

                    // If the parent_state of the node is both done,
                    // the top node could be popped off the stack.
                    // Update the LCA node to be the next top node.
                    if (LCA == stack.pop().getKey() && one_node_found) {
                        LCA = stack.peek().getKey();
                    }

                }
            }

            return null;
        }
    }

}

All Problems

All Solutions