Mastering Binary Tree Lowest Common Ancestor

Introduction

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. The lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor). In this challenge, we will find the lowest common ancestor in a binary tree.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") algorithm/BasicAlgorithmsGroup -.-> algorithm/recursion_dynamic("`Recursion Dynamic`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/BasicConceptsGroup -.-> python/booleans("`Booleans`") python/BasicConceptsGroup -.-> python/type_conversion("`Type Conversion`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/graphs_trees -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} algorithm/recursion_dynamic -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/variables_data_types -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/strings -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/booleans -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/type_conversion -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/conditional_statements -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/tuples -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/function_definition -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/default_arguments -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/classes_objects -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/constructor -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/polymorphism -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/encapsulation -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/raising_exceptions -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} python/build_in_functions -.-> lab-268837{{"`Binary Tree Lowest Common Ancestor`"}} end

Tree Lca

Problem

Given a binary tree and two nodes, find their lowest common ancestor.

Requirements

To solve this problem, we need to consider the following requirements:

The given tree is a binary tree, not a binary search tree.
We cannot assume that the two nodes are already in the tree.
We can assume that the binary tree fits in memory.

Example Usage

Consider the following binary tree:

          _10_
        /      \
       5        9
      / \      / \
     12  3    18  20
        / \       /
       1   8     40

We can test our function with the following inputs and expected outputs:

0, 5 -> None (both nodes are not in the tree)
5, 0 -> None (both nodes are not in the tree)
1, 8 -> 3
12, 8 -> 5
12, 40 -> 10
9, 20 -> 9
3, 5 -> 5

Summary

In this challenge, we have learned how to find the lowest common ancestor in a binary tree. We have considered the requirements and tested our function with different inputs and expected outputs.

Binary Tree Lowest Common Ancestor