Welcome to Subscribe On Youtube

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

  • 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;
                }
            }
        }
    
        // official oj solution https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/
        class Solution {
    
            private TreeNode ans;
    
            public Solution() {
                // Variable to store LCA node.
                this.ans = null;
            }
    
            private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
    
                // If reached the end of a branch, return false.
                if (currentNode == null) {
                    return false;
                }
    
                // Left Recursion. If left recursion returns true, set left = 1 else 0
                int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
    
                // Right Recursion
                int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
    
                // If the current node is one of p or q
                int mid = (currentNode == p || currentNode == q) ? 1 : 0;
    
    
                // If any two of the flags left, right or mid become True
                if (mid + left + right >= 2) {
                    this.ans = currentNode;
                }
    
                // Return true if any one of the three bool values is True.
                return (mid + left + right > 0);
            }
    
            public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
                // Traverse the tree
                this.recurseTree(root, p, q);
                return this.ans;
            }
        }
    
    
        // official oj solution-2 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/
        class Solution {
    
            public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
                // Stack for tree traversal
                Deque<TreeNode> stack = new ArrayDeque<>();
    
                // HashMap for parent pointers
                Map<TreeNode, TreeNode> parent = new HashMap<>();
    
                parent.put(root, null);
                stack.push(root);
    
                // Iterate until we find both the nodes p and q
                while (!parent.containsKey(p) || !parent.containsKey(q)) {
    
                    TreeNode node = stack.pop();
    
                    // While traversing the tree, keep saving the parent pointers.
                    if (node.left != null) {
                        parent.put(node.left, node);
                        stack.push(node.left);
                    }
                    if (node.right != null) {
                        parent.put(node.right, node);
                        stack.push(node.right);
                    }
                }
    
                // Ancestors set() for node p.
                Set<TreeNode> ancestors = new HashSet<>();
    
                // Process all ancestors for node p using parent pointers.
                while (p != null) {
                    ancestors.add(p);
                    p = parent.get(p);
                }
    
                // The first ancestor of q which appears in
                // p's ancestor set() is their lowest common ancestor.
                while (!ancestors.contains(q))
                    q = parent.get(q);
                return q;
            }
    
        }
    
        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;
            }
        }
    
    }
    
    ############
    
    /**
     * 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 || root == p || root == q) return root;
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left == null) return right;
            if (right == null) return left;
            return root;
        }
    }
    
  • // OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        bool findPath(TreeNode *node, TreeNode *target, vector<TreeNode*> &path) {
            if (!node) return false;
            path.push_back(node);
            if (node == target) return true;
            if (findPath(node->left, target, path) || findPath(node->right, target, path)) return true;
            path.pop_back();
            return false;
        }
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<TreeNode*> a, b;
            findPath(root, p, a);
            findPath(root, q, b);
            TreeNode *ans = nullptr;
            for (int i = 0; i < a.size() && i < b.size() && a[i] == b[i]; ++i) ans = a[i];
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    
    class Solution:
        def lowestCommonAncestor(
            self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
        ) -> 'TreeNode':
            if root is None or root == p or root == q:
                return root
            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)
            return root if left and right else (left or right)
    
    ############
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
          return root
    
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
    
        if left and right:
          return root
    
        if root == p or root == q:
          return root
    
        if left:
          return left
        if right:
          return right
        return None
    
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    	if root == nil || root == p || root == q {
    		return root
    	}
    	left := lowestCommonAncestor(root.Left, p, q)
    	right := lowestCommonAncestor(root.Right, p, q)
    	if left == nil {
    		return right
    	}
    	if right == nil {
    		return left
    	}
    	return root
    }
    
  • /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     val: number
     *     left: TreeNode | null
     *     right: TreeNode | null
     *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.left = (left===undefined ? null : left)
     *         this.right = (right===undefined ? null : right)
     *     }
     * }
     */
    
    function lowestCommonAncestor(
        root: TreeNode | null,
        p: TreeNode | null,
        q: TreeNode | null,
    ): TreeNode | null {
        const find = (root: TreeNode | null) => {
            if (root == null || root == p || root == q) {
                return root;
            }
            const left = find(root.left);
            const right = find(root.right);
            if (left != null && right != null) {
                return root;
            }
            if (left != null) {
                return left;
            }
            return right;
        };
        return find(root);
    }
    
    
  • /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {TreeNode} p
     * @param {TreeNode} q
     * @return {TreeNode}
     */
    var lowestCommonAncestor = function (root, p, q) {
        if (!root || root == p || root == q) return root;
        const left = lowestCommonAncestor(root.left, p, q);
        const right = lowestCommonAncestor(root.right, p, q);
        if (!left) return right;
        if (!right) return left;
        return root;
    };
    
    
  • // Definition for a binary tree node.
    // #[derive(Debug, PartialEq, Eq)]
    // pub struct TreeNode {
    //   pub val: i32,
    //   pub left: Option<Rc<RefCell<TreeNode>>>,
    //   pub right: Option<Rc<RefCell<TreeNode>>>,
    // }
    //
    // impl TreeNode {
    //   #[inline]
    //   pub fn new(val: i32) -> Self {
    //     TreeNode {
    //       val,
    //       left: None,
    //       right: None
    //     }
    //   }
    // }
    use std::rc::Rc;
    use std::cell::RefCell;
    impl Solution {
        fn find(
            root: &Option<Rc<RefCell<TreeNode>>>,
            p: &Option<Rc<RefCell<TreeNode>>>,
            q: &Option<Rc<RefCell<TreeNode>>>,
        ) -> Option<Rc<RefCell<TreeNode>>> {
            if root.is_none() || root == p || root == q {
                return root.clone();
            }
            let node = root.as_ref().unwrap().borrow();
            let left = Self::find(&node.left, p, q);
            let right = Self::find(&node.right, p, q);
            match (left.is_some(), right.is_some()) {
                (true, false) => left,
                (false, true) => right,
                (false, false) => None,
                (true, true) => root.clone(),
            }
        }
    
        pub fn lowest_common_ancestor(
            root: Option<Rc<RefCell<TreeNode>>>,
            p: Option<Rc<RefCell<TreeNode>>>,
            q: Option<Rc<RefCell<TreeNode>>>,
        ) -> Option<Rc<RefCell<TreeNode>>> {
            Self::find(&root, &p, &q)
        }
    }
    
    

All Problems

All Solutions