• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

[Solved] Find Lowest Common Ancestor in the Binary Tree

Aniruddha Chaudhari/6075/0
CodeCSE SubjectData StructurePython

In an earlier tutorial, we have seen

  • what is the ancestor of a node in the binary tree?
  • How to find and print all the ancestors of a given node in a Binary tree?

If you have not gone through it, read it here.

In this tutorial, we will find the lowest common ancestor in the binary tree when two nodes are given.

Let’s take the below binary tree example.

reorder, inorder and post order traversal

The node ‘x’ is the lowest common ancestor of given two nodes if two nodes present on either side (left and right) of ‘x’.

Example:

  • The lowest common ancestor of nodes 7 and 3 is 1.
    Node 7 is present in the left branch and 3 is present in the right branch of node 1.
  • The lowest common ancestor of nodes 3 and 6 is 4.
    Node 3 is present in the left branch and 6 is present in the right branch of node 4.

Algorithm to find the lowest common ancestor in the Binary Tree

Here is the simple algorithm to find the lowest common ancestors of two nodes (says ‘a’ and ‘b’) in a binary tree.

  • Find all the ancestors of node ‘a’, save them in the list (says, ancestorsA)
  • Find all the ancestors of node ‘b’., save them in the list (says, ancestorsB)
  • Search for the first common node in the list ancestorsA and ancestorsB. This will give you the lowest common ancestor.

Example:

Let’s find the common ancestor of nodes 3 and 6.

  • Ancestors of node 3: [1, 4]
  • Ancestors of node 6: [5, 4]
  • The first common element is ‘4’. So, the lowest common ancestor of nodes 3 and 6 is ‘4’.

Use this logic to write a code in any programming language you are comfortable with, like C/C++, Java, Python…

This problem was asked to me in one of the Amazon interview round.

Python Program

Here we are maintaining two list ancestorsA and ancestorsB to stores all the ancestors of two nodes nodeA and nodeB.

Code:

#binary tree node structure

ancestorsA=[]
ancestorsB=[]

class node:
  def __init__(self, val, left=None, right=None):
    self.left=left
    self.val=val
    self.right=right

 
#function to print all the ancestors of a given node
def findAncestors(root, val, listAncestors):
  if not root:
    return False
  else:
    if root.val==val:
      return True
    else:
      if findAncestors(root.left,val, listAncestors) or \
        findAncestors(root.right,val, listAncestors):
        listAncestors.append(root.val)
        return True
 
#create binary tree
root=node(4)
root.left=node(1)
root.right=node(5)
root.left.left=node(7)
root.left.right=node(3)
root.right.right=node(6)
 

nodeA=6
nodeB=3

findAncestors(root, nodeA, ancestorsA)
findAncestors(root, nodeB, ancestorsB)


for i in range(0, min(len(ancestorsA), len(ancestorsB))):
  if ancestorsA[i]==ancestorsB[i]:
    print("The lowest common ancestor in the binary tree \ 
      for nodes %d and %d is %d." \
      %(nodeA, nodeB, ancestorsA[i]))

Output:

The lowest common ancestor in the binary tree for nodes 6 and 3 is 4.

Note: To find common ancestors, you don’t need to sort the nodes in a Binary tree. This solution works even if the nodes are in an unsorted order.

Complexity

To calculate the ancestors of any node in the binary tree takes the time of O(n).

A total number of ancestors to any node can not exceed log(n). In the worst case, it takes O(log(n)) to find the first common ancestor node.

So, the total complexity of this problem is O(n)+O(n)+O(log(n)) which is equivalent to O(n).

 

Binary TreeData Structure
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Leave a Reply Cancel reply

Binary Tree (BT)

  1. BT- Introduction
  2. BT- Create Binary Tree
  3. BT- Pre/In/Post Order Traversal
  4. BT- Height 
  5. BT- Level Order Traversal
  6. BT- Min and Max Heap
  7. BT- Parent of a Given Node
  8. BT- Ancestors of Given Node
  9. BT- Lowest Common Ancestor
  10. BT- Check Sub Tree

Binary Search Tree (BST)

  1. BST- Introduction
  2. BST- Search Node
  3. BST- Insert Node

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard