Sequentially traverse the tree in reverse preorder fashion

Question

Sequentially traverse the tree in reverse preorder fashion

My goal is to locate the element that is positioned directly above another element in the layout. This could mean the element is nested within several levels of the DOM structure, or it may involve moving up a few levels in the hierarchy. For instance:

div.a        
  div.b      
    div.c      
    div.d    
      div.e  
        div.f
    div.g    
  div.h      
  div.i      
div.j        
div.k

In this example, .b, .h, .i are immediate children of .a. So if I were to call getBefore($('.h'));, I would expect to receive .g. To achieve this, a pre-order reverse search would need to start at div.b.

The issue I'm encountering is that without a complete global recursive scan, it becomes challenging to handle situations like getBefore($('.c'));, where the expected result would be .b. The routine, without knowledge of the complete hierarchy, may mistakenly retrieve the bottom-most element .g after examining .b.

Considering this, it appears that a recursive implementation may not be a straightforward solution, as the routine does not receive the root node as input, but rather a node within a tree of unknown structure. In light of this, what would be a reasonable iterative approach? The DOM provides mechanisms to navigate to parent nodes, access previous siblings, and retrieve a list of child nodes for any given element.

javascript dom recursion tree depth-first-search

Answer 1

Answer №1

To achieve the desired outcome, I utilized a unique approach. It involves employing a regular recursive preorder traversal function in conjunction with an iterative routine that is able to determine the appropriate direction to traverse.

The iterative routine begins by selecting a node and then navigating through the parent's sibling list using the node = node.previousSibling method. Once it reaches the top of the tree, it moves to the parent node by using node = node.parentNode. During each step of this process, a method is invoked that implements a standard recursive preorder search algorithm to locate the final relevant item in the node's rooted tree. For example, when accessing .g, it eventually leads to .f because $('.g')[0].previousSibling refers to .d which, in turn, contains .f.

Interestingly, when executing the getAfter() function to move in the forward direction, recursion is not necessary. Nevertheless, incorporating recursion does contribute to a more refined and elegant code structure.

Answer 2

To achieve the desired outcome, I utilized a unique approach. It involves employing a regular recursive preorder traversal function in conjunction with an iterative routine that is able to determine the appropriate direction to traverse.

The iterative routine begins by selecting a node and then navigating through the parent's sibling list using the node = node.previousSibling method. Once it reaches the top of the tree, it moves to the parent node by using node = node.parentNode. During each step of this process, a method is invoked that implements a standard recursive preorder search algorithm to locate the final relevant item in the node's rooted tree. For example, when accessing .g, it eventually leads to .f because $('.g')[0].previousSibling refers to .d which, in turn, contains .f.

Interestingly, when executing the getAfter() function to move in the forward direction, recursion is not necessary. Nevertheless, incorporating recursion does contribute to a more refined and elegant code structure.

Answer 3

Answer №2

One interesting concept in preorder traversal utilizing a stack is to prioritize pushing the right child before the left child. This ensures that the left child is processed before the right child.

class Node {
    int key;
    Node left, right;

    public Node() {}

    public Node(int key) {
        this.key = key;
    }
}

public List<Integer> iterativePreOrder() {
    List<Integer> list = new ArrayList<>();
    Stack<Node> nodeStack = new Stack<>();

    nodeStack.push(root);

    while (!nodeStack.empty()) {
         Node node = nodeStack.pop();
         list.add(node.key);

         if (null != node.right) nodeStack.push(node.right);
         if (null != node.left) nodeStack.push(node.left);
    }
    return list;
}

Answer 4

One interesting concept in preorder traversal utilizing a stack is to prioritize pushing the right child before the left child. This ensures that the left child is processed before the right child.

class Node {
    int key;
    Node left, right;

    public Node() {}

    public Node(int key) {
        this.key = key;
    }
}

public List<Integer> iterativePreOrder() {
    List<Integer> list = new ArrayList<>();
    Stack<Node> nodeStack = new Stack<>();

    nodeStack.push(root);

    while (!nodeStack.empty()) {
         Node node = nodeStack.pop();
         list.add(node.key);

         if (null != node.right) nodeStack.push(node.right);
         if (null != node.left) nodeStack.push(node.left);
    }
    return list;
}

Sequentially traverse the tree in reverse preorder fashion

Answer №1

Answer №2

Similar questions

How to manage rejections in async/await within the Array#map method

Function that recursively checks for the existence of an ID within a nested object structure

Stopping the setTimeout function triggered by a click event in a Reactjs application

Combining Repetitive Elements in an Array

What is the process for creating a sub-menu for a dropdown menu item in Bootstrap 5?

Finding the Modular Reciprocal with JavaScript

Transfer JSON data between controllers without utilizing Services or Factory in AngularJS during routing

"How to automatically populate an input field with a value when the page loads in an

How can I preserve the line break in a textarea using PHP?

Possible revised text: "Exploring methods for verifying elements within a div using Selenium

Restrict the PHP generated Json response to display only the top 5 results

An issue encountered with react-router-dom and the useLocation() function

"Using JavaScript to trigger a button click event, and then

Ways to delete a particular query parameter from a URL in Next.js

I am encountering an issue with my authentication system where it is returning

Javascript's associative arrays: a versatile tool for data organization

The scroll event listener activates based on the distance I have scrolled

What is the mechanism behind the operation of the inherits feature in Node.js?

Provide users with the option to select a specific destination for saving their file

Refresh Form Following Submission