Kth Ancestor in Binary Tree using JavaScript

LCA in Binary Tree using JavaScript

Given a binary tree and a node in this tree, our task is to find the k-th ancestor of the specified node in JavaScript. If no such ancestor exists, or when k exceeds the depth of the node, the function should return null.

Example:

Input: Node = 5, k = 2
Output: 1

Approach

First, calculate the depth of each node, the number of edges from the node to the tree’s root and store it along with each node’s parent.
Using the stored information, trace back from the given node to its k-th ancestor by using the depth and parent pointers.
Traverse the binary tree to record each node’s parent and depth. This can be done using a simple BFS.
For the given node, use the depth information to jump back k levels to find and return the k-th ancestor.

Example: The example below shows kth ancestor in Binary tree using JavaScript.

JavaScript

class TreeNode {
    constructor(value = 0, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

function kthAncestor(root, node, k) {
    let parentMap = new Map();  
    let depthMap = new Map();   

    function buildMaps(node, parent = null, depth = 0) {
        if (node !== null) {
            parentMap.set(node, parent);
            depthMap.set(node, depth);
            buildMaps(node.left, node, depth + 1);
            buildMaps(node.right, node, depth + 1);
        }
    }

    buildMaps(root);

    let ancestor = node;

    while (k > 0 && ancestor !== null) {
        ancestor = parentMap.get(ancestor);
        k--;
    }

    return ancestor ? ancestor.value : null;
}

let root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3, null, new TreeNode(6))
);

let node = root.left.right;
console.log(kthAncestor(root, node, 2));

Output

Time Complexity: O(n) time, where n is the number of nodes in the tree.

Space Complexity: O(n).

Tags:

#JavaScript-Program #JavaScript #Web Technologies

LCA in Binary Tree using JavaScript

Kth Ancestor in Binary Tree using JavaScript

Approach

Contact Us