Identifying the Kth Ancestor in a Binary Tree
Sun Mar 31 2024 kthAncestorDFS:
A function ingeniously designed to traverse the binary tree using depth-first search (DFS) techniques to locate the kth ancestor of a specified node. Starting from the root, it explores each branch, searching for the target node. Upon locating the target, the function initiates a backward trace, decrementing the k value with each upward step through the ancestors. When k reaches zero, the current node is identified as the kth ancestor, marking the end of the search. This method effectively combines the principles of DFS with a counter mechanism to pinpoint the precise ancestor, showcasing the versatility of DFS in addressing specific hierarchical queries within a binary tree.
1class Node {
2 constructor(data) {
3 this.data = data;
4 this.left = null;
5 this.right = null;
6 }
7}
8
9let temp = null;
10let k = 0;
11
12function kthAncestorDFS(root, node) {
13 if (root === null) return null;
14
15 if (root.data === node || (temp = kthAncestorDFS(root.left, node)) !== null || (temp = kthAncestorDFS(root.right, node)) !== null) {
16 if (k > 0) k--;
17 else if (k === 0) {
18 return root.data;
19 }
20 return root;
21 }
22 return null;
23}
24
25function newNode(data) {
26 let temp = new Node();
27 temp.data = data;
28 temp.left = temp.right = null;
29 return temp;
30}
31
32let root = newNode(1);
33root.left = newNode(2);
34root.right = newNode(3);
35root.left.left = newNode(4);
36root.left.right = newNode(5);
37k = 2;
38let node = 5;
39let ancestor = kthAncestorDFS(root, node);
40
41if (ancestor !== null) console.log('Kth ancestor is: ' + ancestor);
42else console.log('-1');
43