Find the predecessors of a specific node within a tree structure

Question

Find the predecessors of a specific node within a tree structure

Looking for help with my tree structure. I am trying to retrieve all ancestors of a specific node in the tree, where each node can have multiple children and each child can also be a parent.

https://i.sstatic.net/cPqSM.png

Below is the code I've written to achieve this, but it consistently returns undefined. Any suggestions or advice would be greatly appreciated.

  getAncestors(nodeId: number, ancestors: number[] = []): number[] {
    if (this.nodeId === nodeId) {
      return ancestors;
    }
    
    if (this.children.length > 0) {
      ancestors.push(this.nodeId);
    }
    
    for (const child of this.children) {
      child.getAncestors(nodeId, ancestors);
    }

    return ancestors;
  }

javascript tree treeview

Answer 1

Answer №1

Just by reading the following sentence, it should raise a major concern:

child.getAncestors(nodeId, ancestors);

If I have to ask my children who their parents are every time someone inquires about my ancestry, then the process is not only highly inefficient but also runs the risk of encountering an infinite loop. It's best to refrain from involving children in this function altogether.

A more suitable solution would largely depend on the overall structure of the node class. For instance, if each node has direct access to the root, we could start our search from the root and trace back to the original node while keeping track of all traversed nodes along the way. However, this approach might become convoluted.

An alternative, simpler option would be to maintain a record of all ancestors as each node gets created. Take a file system for example, where an absolute path is essential for accessing any file. Updating this list of ancestors becomes necessary if frequent node reorganization and movement are anticipated.

If nodes had direct access to their parents, accomplishing this task could be achieved through a straightforward while loop and a pointer:

ancestors = [];
nodePtr = this;
while (nodePtr !== root) {
    nodePtr = nodePtr.parent();
    ancestors.push(nodePtr);
}
ancestors.push(root);

Answer 2

Just by reading the following sentence, it should raise a major concern:

child.getAncestors(nodeId, ancestors);

If I have to ask my children who their parents are every time someone inquires about my ancestry, then the process is not only highly inefficient but also runs the risk of encountering an infinite loop. It's best to refrain from involving children in this function altogether.

A more suitable solution would largely depend on the overall structure of the node class. For instance, if each node has direct access to the root, we could start our search from the root and trace back to the original node while keeping track of all traversed nodes along the way. However, this approach might become convoluted.

An alternative, simpler option would be to maintain a record of all ancestors as each node gets created. Take a file system for example, where an absolute path is essential for accessing any file. Updating this list of ancestors becomes necessary if frequent node reorganization and movement are anticipated.

If nodes had direct access to their parents, accomplishing this task could be achieved through a straightforward while loop and a pointer:

ancestors = [];
nodePtr = this;
while (nodePtr !== root) {
    nodePtr = nodePtr.parent();
    ancestors.push(nodePtr);
}
ancestors.push(root);

Answer 3

Answer №2

I recently tackled a similar issue by utilizing a recursive function.

The recursive function must return a boolean value to indicate whether the node has been found, serving as the signal for adding ancestors. Additionally, it should include an array list in the parameter list to store the ancestors. For further details, you can check out the following link: https://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/

// JavaScript program to print ancestors of given node
     
    class Node
    {
        constructor(item) {
              this.data = item;
            this.left = null;
            this.right = null;
            this.nextRight = null;
        }
    }
     
    let root;
    
    /* If target is present in tree, then prints the ancestors
       and returns true, otherwise returns false. */
    function printAncestors(node, target)
    {
         /* base cases */
        if (node == null)
            return false;
    
        if (node.data == target)
            return true;
    
        /* If target is present in either left or right subtree
           of this node, then print this node */
        if (printAncestors(node.left, target)
                || printAncestors(node.right, target))
        {
            document.write(node.data + " ");
            return true;
        }
    
        /* Else return false */
        return false;
    }
     
    /* Construct the following binary tree
                    1
                  /   \
                 2     3
                /  \
               4    5
              /
             7
          */
    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.left.left.left = new Node(7);
 
    printAncestors(root, 7);

Answer 4

I recently tackled a similar issue by utilizing a recursive function.

The recursive function must return a boolean value to indicate whether the node has been found, serving as the signal for adding ancestors. Additionally, it should include an array list in the parameter list to store the ancestors. For further details, you can check out the following link: https://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/

// JavaScript program to print ancestors of given node
     
    class Node
    {
        constructor(item) {
              this.data = item;
            this.left = null;
            this.right = null;
            this.nextRight = null;
        }
    }
     
    let root;
    
    /* If target is present in tree, then prints the ancestors
       and returns true, otherwise returns false. */
    function printAncestors(node, target)
    {
         /* base cases */
        if (node == null)
            return false;
    
        if (node.data == target)
            return true;
    
        /* If target is present in either left or right subtree
           of this node, then print this node */
        if (printAncestors(node.left, target)
                || printAncestors(node.right, target))
        {
            document.write(node.data + " ");
            return true;
        }
    
        /* Else return false */
        return false;
    }
     
    /* Construct the following binary tree
                    1
                  /   \
                 2     3
                /  \
               4    5
              /
             7
          */
    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.left.left.left = new Node(7);
 
    printAncestors(root, 7);

Find the predecessors of a specific node within a tree structure

Answer №1

Answer №2

Similar questions

Customize YouTube iframe styles in Angular 4+ with TypeScript

I made a mistake with my git repository. Should I try to fix it or just start fresh?

The state of the Toggle Button in Material UI

What is the best way to insert a newline in a shell_exec command in PHP

What are some solutions for managing SubPixel Handling issues on an iPhone?

Ajax success handler failing to process JSON response despite receiving status code 200 or 304

Is there a way to apply -webkit-text-fill-color using pure vanilla JavaScript?

Is it possible to execute "green arrow" unit tests directly with Mocha in IntelliJ IDEA, even when Karma and Mocha are both installed?

Having difficulty accessing the sound file despite inputting the correct path. Attempts to open it using ./ , ../ , and ../../ were unsuccessful

Mastering the art of sending HTML emails with Express.js

Choose individual characters one by one

The collada loader in three.js assigns the UV texture's color to every model in the scene

What is the best way to continuously click a JavaScript link until it disappears?

Issues with jQuery not detecting click events

Translating Encryption from Javascript to Ruby

The Google Books API has encountered an authentication error with status code 401

creating links using json2html

loops with nested MongoDB queries

Enhance Your Forms with Bootstrap 4 Validation Using JavaScript/jQuery

"Exploring One Direction: A bright spotlight on navigating with PointerLockControls in Threejs