java - How to find right subtree in a recursive preorder traversal - Stack Overflow

admin管理员组

文章数量:1402299

Hello I'm trying to find the next element of a node in a preorder traversal in a binary tree

eg: consider a BT

    1
   / \
  2   3
 / \   \
4   5   6
   /
  7

i want to write a recursive algorithm such that if the method input is a node like preOrder(2) -> 5

similarly preOrder(5) -> 7

But the problem arises when i have to visit the right subtree of the root node such as preOrder(7) -> 3

This is my code, I'm new to programming, so this might not be clean code. Aprreciate any help thanks

     public E preordernextRecursive(Node<E> node) {
        if (node == null) {
            return null;
        } 
        else if (node.left != null) {
            return node.left.element; 
        } 
        else if (node.right != null) {
            return node.right.element; 
        } 
        else if (node.parent != null && node.parent.left == node && node.parent.right != null) {
            return node.parent.right.element;  
        }
        else if((node.parent.left == node || node.parent.right == node) && node.left  == null && node.right == null ) {
             return preordernextRecursive(node.parent); 
        }
        return null;
    }

Hello I'm trying to find the next element of a node in a preorder traversal in a binary tree

eg: consider a BT

    1
   / \
  2   3
 / \   \
4   5   6
   /
  7

i want to write a recursive algorithm such that if the method input is a node like preOrder(2) -> 5

similarly preOrder(5) -> 7

But the problem arises when i have to visit the right subtree of the root node such as preOrder(7) -> 3

This is my code, I'm new to programming, so this might not be clean code. Aprreciate any help thanks

     public E preordernextRecursive(Node<E> node) {
        if (node == null) {
            return null;
        } 
        else if (node.left != null) {
            return node.left.element; 
        } 
        else if (node.right != null) {
            return node.right.element; 
        } 
        else if (node.parent != null && node.parent.left == node && node.parent.right != null) {
            return node.parent.right.element;  
        }
        else if((node.parent.left == node || node.parent.right == node) && node.left  == null && node.right == null ) {
             return preordernextRecursive(node.parent); 
        }
        return null;
    }

• java

Share Improve this question Follow asked Mar 21 at 21:22 user29829599user29829599 311 bronze badge

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

The problem is how you handle the case when your tree reaches the bottom.

In you case if you use if statement it should keep oupting 7 while you do preOrder(7) because

When you do the recursion

return preordernextRecursive(node.parent);

Node will become 5 and fall in the below statement since node.left = 7

 else if (node.left != null) {
            return node.left.element; 
        } 

---

Solution ( While loop )

Instead of using if else you can try using while loop:

Node<E> current = node;
    while (current.parent != null) {
        if (current.parent.left == current && current.parent.right != null) {
            return current.parent.right.element;
        }
        current = current.parent;
    }

This simply keep moving up until it reached the root element and return the node of right subtree without recursion part, which should have a slightly better space complexity.

probably not the best solutions but should be able to solve your problem !

This is my first time to comment here (and literally just made an account)

Hope this is clear for you !

本文标签： javaHow to find right subtree in a recursive preorder traversalStack Overflow