Binary Search Tree is traversed in the following order recursively Right root Left?

Question

Usually we traverse the Binary search tree either in order ,preorder or post order.But what happens when we traverse the Binary Search Tree in the following recursive order From Right - Root -Left?

Suppose if i store the values in an array and whether its time complexity increases when we do the traversal in this order when compared to preorder traversal.

AndyG AndyG · Accepted Answer · 2016-07-06T18:05:23

Let's use an example binary search tree:

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

In-order traversal (Left tree, root, right tree)

2 3 4 5 6 7 8

How did we get that?

Pseudo code:

InorderTraversal(root)
{
   if root is not null:
      InorderTraversal(root.left)
      print root
      InorderTraversal(root.right)
}

Let's play computer on our tree

Start at root (5)
Root (5) is not null, so visit left
Root (3) is not null so visit left
Root (2) is not null so visit left
Root (null) is null, return
print 2
Visit right tree of 2
Root (null) is null, return
print root (3)
Visit right tree of 3
Root (4) is not null, visit left
Root (null) is null, return
print root (4)
Visit right tree of 4
root (null) is null, return
Print root (5)
Visit right tree of 5
Root (7) is not null
...
print root (8)
visit right subtree of root (8)
root (null) is null, return

Right root left traversal

8 7 6 5 4 3 2

Pseudo code:

RightRootLeftTraversal(root)
{
   if root is not null:
      RightRootLeftTraversal(root.right)
      print root
      RightRootLeftTraversal(root.left)
}

As you can see, this is in exactly the opposite order as an in-order traversal. On a binary search tree, we will get a reverse-ordered traversal.

The number of operations is identical to a preorder traversal, which is O(n) because we visit every node one time.

Binary Search Tree is traversed in the following order recursively Right root Left?

1 Answers