Determine whether two nodes lie on the same path in a binary tree

Given a binary tree and two tree pointers, x and y, write an efficient algorithm to check if they lie on the same root-to-leaf path in the binary tree. In other words, determine whether x is an ancestor of y, or x is a descendant of y. The algorithm should work in minimal time for numerous inputs.

For example, consider the following binary tree. The nodes 2 and 8 lie on the same root-to-leaf path, while nodes 5 and 9 do not lie on the same root-to-leaf path.

Binary Tree

Practice this problem

Prerequisite:

Arrival and departure time of vertices in DFS

A simple solution would be to traverse the binary tree and check if the node x lies in either the left or right subtree of y, or vice versa. However, if m lookup calls are made to the binary tree having n nodes, then this solution takes O(n.m) time. The following solution reduces the time complexity to O(m + n).

The idea is to find the arrival and departure time of each tree node by doing a Depth–first search (DFS) on the binary tree. For a binary tree, the DFS algorithm is a simple preorder or postorder traversal. The arrival time is the time when the DFS first explores the node and the departure time is the time at which all children of the node are visited, and we are ready to backtrack.

Therefore, before exploring the left and right child of any node in DFS, mark the arrival time of that node, and after exploring the left and right child of the node, mark its departure time. For example, here are each tree node’s arrival and departure time on traversing the above binary tree in a preorder fashion.

Node 1 —> (1, 28)
Node 2 —> (2, 17)
Node 4 —> (3, 12)
Node 8 —> (4, 5)
Node 9 —> (6, 11)
Node 12 —> (7, 8)
Node 13 —> (9, 10)
Node 5 —> (13, 16)
Node 10 —> (14, 15)
Node 3 —> (18, 27)
Node 6 —> (19, 20)
Node 7 —> (21, 26)
Node 11 —> (22, 25)
Node 14 —> (23, 24)

Important Observations:

If x is an ancestor of y, the relation between the arrival and departure time is:

arrival[x] < arrival[y] < departure[y] < departure[x]

Alternatively, if x is a descendant of y, the relation between the arrival and departure time is:

arrival[y] < arrival[x] < departure[x] < departure[y]

The algorithm can be implemented as follows in C++, Java, and Python:

C++

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

#include <iostream>

#include <unordered_map>

using namespace std;

// Data structure to store a binary tree node

struct Node

{

int data;

Node *left, *right;

Node(int data)

{

this->data = data;

this->left = this->right = nullptr;

}

};

// Utility function to print a binary tree using preorder traversal

void printTree(Node* root,

unordered_map<Node*, int> &arrival,

unordered_map<Node*, int> &departure)

{

// base case

if (root == nullptr) {

return;

}

// print the root node with its arrival and departure time

cout << "Node " << root->data << " (" << arrival[root] << ", "

<< departure[root] << ")" << endl;

// recur for the left child

printTree(root->left, arrival, departure);

// recur for the right child

printTree(root->right, arrival, departure);

}

// Recursive function to perform the DFS traversal on a binary tree

// and set the arrival and departure time for each tree node

void performDFS(Node* root,

unordered_map<Node*, int> &arrival,

unordered_map<Node*, int> &departure,

int &time)

{

// base case

if (root == nullptr) {

return;

}

// set arrival time of the root node

arrival[root] = ++time;

// process the left child

performDFS(root->left, arrival, departure, time);

// process the right child

performDFS(root->right, arrival, departure, time);

// set departure time of the root node

departure[root] = ++time;

}

// Function to check if two nodes `x` and `y` lie on the same path in a binary tree

bool isAncestorOrDescendant(Node* x, Node* y,

unordered_map<Node*, int> &arrival,

unordered_map<Node*, int> &departure)

{

if (!arrival[x] || !arrival[y]) {

cout << "Node " << x->data << " or Node " << y->data <<

" is not the actual node in the tree";

return false;

}

bool isAncestor = arrival[x] < arrival[y] && departure[x] > departure[y];

bool isDescendant = arrival[y] < arrival[x] && departure[y] > departure[x];

if (isAncestor)

{

cout << "Node " << x->data << " is an ancestor of Node "

<< y->data << endl;

}

else if (isDescendant)

{

cout << "Node " << x->data << " is a direct descendant of Node "

<< y->data << endl;

}

else {

cout << "Node " << x->data << " is a neither an ancestor nor a "

"descendant of Node " << y->data << endl;

}

return isAncestor || isDescendant;

}

int main()

{

// construct a binary tree as per the above diagram

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

root->right->left = new Node(6);

root->right->right = new Node(7);

root->left->left->left = new Node(8);

root->left->left->right = new Node(9);

root->left->right->right = new Node(10);

root->right->right->left = new Node(11);

root->left->left->right->left = new Node(12);

root->left->left->right->right = new Node(13);

root->right->right->left->left = new Node(14);

// Create a map to store the arrival time of a tree node

unordered_map<Node*, int> arrival;

// Create a map to store the departure time of a tree node

unordered_map<Node*, int> departure;

// start with time 0

int time = 0;

// perform preorder traversal on the binary tree and set the

// arrival and departure time for each tree node

performDFS(root, arrival, departure, time);

// printTree(root, arrival, departure);

isAncestorOrDescendant(root->right, root->right->right->left->left,

arrival, departure);

isAncestorOrDescendant(root->left->left->right->left, root->left,

arrival, departure);

isAncestorOrDescendant(root->left->left, root->left->right,

arrival, departure);

isAncestorOrDescendant(new Node(root->left->left->data), root->left->right,

arrival, departure);

return 0;

}

Download Run Code

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

import java.util.HashMap;

import java.util.Map;

// A class to store a binary tree node

class Node

{

int data;

Node left, right;

Node(int data)

{

this.data = data;

this.left = this.right = null;

}

class Main

{

// Utility function to print a binary tree using preorder traversal

public static void printTree(Node root,

Map<Node, Integer> arrival,

Map<Node, Integer> departure) {

// base case

if (root == null) {

return;

}

// print the root node with its arrival and departure time

System.out.println("Node " + root.data + " (" + arrival.get(root) + ", "

+ departure.get(root) + ")");

// recur for the left child

printTree(root.left, arrival, departure);

// recur for the right child

printTree(root.right, arrival, departure);

}

// Recursive function to perform the DFS traversal on a binary tree

// and set the arrival and departure time for each tree node

public static int performDFS(Node root,

Map<Node, Integer> arrival,

Map<Node, Integer> departure,

int time) {

// base case

if (root == null) {

return time;

}

// set arrival time of the root node

arrival.put(root, ++time);

// process the left child

time = performDFS(root.left, arrival, departure, time);

// process the right child

time = performDFS(root.right, arrival, departure, time);

// set departure time of the root node

departure.put(root, ++time);

return time;

}

// Function to check if two nodes `x` and `y` lie on the same path in a binary tree

public static boolean isAncestorOrDescendant(Node x, Node y,

Map<Node, Integer> arrival,

Map<Node, Integer> departure)

{

if (!arrival.containsKey(x) || !arrival.containsKey(y)) {

System.out.println("Node " + x.data + " or Node " + y.data +

" is not the actual node in the tree");

return false;

}

boolean isAncestor = arrival.get(x) < arrival.get(y) &&

departure.get(x) > departure.get(y);

boolean isDescendant = arrival.get(y) < arrival.get(x) &&

departure.get(y) > departure.get(x);

if (isAncestor) {

System.out.println("Node " + x.data + " is an ancestor of Node " + y.data);

}

else if (isDescendant) {

System.out.println("Node " + x.data + " is a direct descendant of Node " +

y.data);

}

else {

System.out.println("Node " + x.data + " is a neither an ancestor nor a " +

"descendant of Node " + y.data);

}

return isAncestor || isDescendant;

}

public static void main(String[] args)

{

// construct a binary tree as per the above diagram

Node root = new Node(1);

root.left = new Node(2);

root.right = new Node(3);

root.left.left = new Node(4);

root.left.right = new Node(5);

root.right.left = new Node(6);

root.right.right = new Node(7);

root.left.left.left = new Node(8);

root.left.left.right = new Node(9);

root.left.right.right = new Node(10);

root.right.right.left = new Node(11);

root.left.left.right.left = new Node(12);

root.left.left.right.right = new Node(13);

root.right.right.left.left = new Node(14);

// create a map to store the arrival time of a tree node

Map<Node, Integer> arrival = new HashMap<>();

// create a map to store the departure time of a tree node

Map<Node, Integer> departure = new HashMap<>();

// start with time 0

int time = 0;

// perform preorder traversal on the binary tree and set the

// arrival and departure time for each tree node

performDFS(root, arrival, departure, time);

// printTree(root, arrival, departure);

isAncestorOrDescendant(root.right, root.right.right.left.left,

arrival, departure);

isAncestorOrDescendant(root.left.left.right.left, root.left,

arrival, departure);

isAncestorOrDescendant(root.left.left, root.left.right, arrival, departure);

isAncestorOrDescendant(new Node(root.left.left.data), root.left.right,

arrival, departure);

}

Download Run Code

Python

100

101

102

103

104

105

106

107

# A class to store a binary tree node

class Node:

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

self.data = data

self.left = left

self.right = right

def __repr__(self):

return str(self.data)

# Utility function to print a binary tree using preorder traversal

def printTree(root, arrival, departure):

# base case

if root is None:

return

# print the root node with its arrival and departure time

print(f'Node {root.data} ({arrival[root]}, {departure[root]})')

# recur for the left child

printTree(root.left, arrival, departure)

# recur for the right child

printTree(root.right, arrival, departure)

# Recursive function to perform the DFS traversal on a binary tree

# and set the arrival and departure time for each tree node

def performDFS(root, arrival, departure, time=0):

# base case

if root is None:

return time

# set arrival time of the root node

time += 1

arrival[root] = time

# process the left child

time = performDFS(root.left, arrival, departure, time)

# process the right child

time = performDFS(root.right, arrival, departure, time)

# set departure time of the root node

time += 1

departure[root] = time

return time

# Function to check if two nodes `x` and `y` lie on the same path in a binary tree

def isAncestorOrDescendant(x, y, arrival, departure):

if x not in arrival or y not in departure:

print(f'Node {x} or Node {y} is not the actual node in the tree')

return False

isAncestor = arrival[x] < arrival[y] and departure[x] > departure[y]

isDescendant = arrival[y] < arrival[x] and departure[y] > departure[x]

if isAncestor:

print(f'Node {x} is an ancestor of Node {y}')

elif isDescendant:

print(f'Node {x} is a direct descendant of Node {y}')

else:

print(f'Node {x} is a neither an ancestor nor a descendant of Node {y}')

return isAncestor or isDescendant

if __name__ == '__main__':

# construct a binary tree as per the above diagram

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.left = Node(6)

root.right.right = Node(7)

root.left.left.left = Node(8)

root.left.left.right = Node(9)

root.left.right.right = Node(10)

root.right.right.left = Node(11)

root.left.left.right.left = Node(12)

root.left.left.right.right = Node(13)

root.right.right.left.left = Node(14)

# create a dictionary to store the arrival time of a tree node

arrival = {}

# create a dictionary to store the departure time of a tree node

departure = {}

# perform preorder traversal on the binary tree and set the

# arrival and departure time for each tree node

performDFS(root, arrival, departure)

# printTree(root, arrival, departure)

isAncestorOrDescendant(root.right, root.right.right.left.left, arrival, departure)

isAncestorOrDescendant(root.left.left.right.left, root.left, arrival, departure)

isAncestorOrDescendant(root.left.left, root.left.right, arrival, departure)

isAncestorOrDescendant(Node(root.left.left.data), root.left.right, arrival, departure)

Download Run Code

Output:

Node 3 is an ancestor of Node 14
Node 12 is a direct descendant of Node 2
Node 4 is a neither an ancestor nor a descendant of Node 5
Node 4 or Node 5 is not the actual node in the tree

The time complexity of the above solution is O(n + m), where n is the total number of nodes in the binary tree and m is the total number of lookups. We can do the constant-time lookups any number of times once the binary tree is preprocessed.

Determine whether two nodes lie on the same path in a binary tree

C++

Java

Python

Share this: