CODEWITHSUNDEEP
arraysalgorithmrecursiontreetime-complexity
user6428595
user6428595

Reputation:

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

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.

Upvotes: 1

Views: 2333

Answers (1)

AndyG
AndyG

Reputation: 41145

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.

Upvotes: 1

Related Questions