Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

First Common Ancestor

就活 binary tree グラフ理論

problem

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

how to solve

Starting from root node and check whether p or q is existed in subtree. If left subtree includes one node and right subtree includes the other node, we can decided that the current node is lowest common ancestor.

code