Lowest common ancestor in a Binary Tree

Medium

Given the root node of a binary tree that contains nodes with numbers along with 2 nodes in the tree, find the lowest common ancestor.

The lowest common ancestor is the root node of the smallest subtree that contains both input nodes.

For example, if your function is given the following binary tree along with the two nodes with the data -4 and 7:

The lowest common ancestor is the node that contains 6.

Each node in the binary tree is an instance of BinaryTreeNode below. note that you don't have access to the parent node.

Try it

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def tree_lca(root: BinaryTreeNode, node1: BinaryTreeNode, node2: BinaryTreeNode) -> BinaryTreeNode:
    # implement tree_lca
    return None

1class BinaryTreeNode:
2    def __init__(self, data):
3        self.data = data
4        self.left = None
5        self.right = None
6
7def tree_lca(root: BinaryTreeNode, node1: BinaryTreeNode, node2: BinaryTreeNode) -> BinaryTreeNode:
8    # implement tree_lca
9    return None
10

Solution

9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

1.Inorder TraversalEasy
2.Tree SumEasy
3.Tree HeightEasy
4.LCAMedium
5.Max Path SumHard
6.Search mazeMedium
7.Number of islandsMedium
8.Kth SmallestMedium
9.Sort K ArraysHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.