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

236 - Lowest Common Ancestor of a Binary Tree

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions