Sorted binary tree.svg

Tree traversal – Wikibooks, open books for an open world

A tree is a particular case of a graph, and due to this fact the graph traversal algorithms of the earlier chapter additionally apply to timber.
A graph traversal can begin at any node, however within the case of a tree the traversal at all times begins on the root node. Binary timber will be traversed in three extra methods. The next tree might be used because the recurring instance.

Sorted binary tree.svg

Breadth-first[edit]

Traversing a tree in breadth-first order signifies that after visiting a node X, all of X’s youngsters are visited, then all of X’s ‘grand-children’ (i.e. the youngsters’s youngsters), then all of X’s ‘great-grand-children’, and so on. In different phrases, the tree is traversed by sweeping by way of the breadth of a stage earlier than visiting the subsequent stage down, as proven on this animation:

Animated instance of a breadth-first traversal

The youngsters of a node could also be visited in any order, however keep in mind the algorithm makes use of a queue, so if a node X is enqueued (gray within the animation) earlier than node Y, then X’s youngsters might be visited (black within the animation) earlier than Y’s youngsters. For the instance tree in the beginning of this chapter, two potential breadth-first traversals are F B G A D I C E H and F G B I D A H E C. Within the second traversal, G is visited earlier than B, so I is visited earlier than A and D.

Train: Breadth First Traversal

Listing two different potential breadth-first traversals of the identical tree.

Reply:

Since F, B and D every have two youngsters, there are in complete 2*2*2=8 potential breadth-first traversals:

  1. F B G A D I C E H
  2. F B G A D I E C H
  3. F B G D A I C E H
  4. F B G D A I E C H
  5. F G B I A D H C E
  6. F G B I A D H E C
  7. F G B I D A H C E
  8. F G B I D A H E C

The primary and final traversals had been already given above, so you can have listed some other two.

Depth-first[edit]

Because the title implies, a depth-first traversal will go down one department of the tree so far as potential, i.e. till it stops at a leaf, earlier than attempting some other department. The assorted branches ranging from the identical guardian could also be explored in any order. For the instance tree, two potential depth-first traversals are F B A D C E G I H and F G I H B D E C A.

Train: Breadth First Traversal

Listing two different potential depth-first traversals of the identical tree.

Reply:

Since F, B and D every have two youngsters, there are in complete 2*2*2=8 potential depth-first traversals:

  1. F B A D C E G I H
  2. F B A D E C G I H
  3. F B D C E A G I H
  4. F B D E C A G I H
  5. F G I H B A D C E
  6. F G I H B A D E C
  7. F G I H B D C E A
  8. F G I H B D E C A

The primary and final traversals had been already given above, so you can have listed some other two.

Train: Depth and Breadth First Traversal

Listing one breadth-first and one depth-first traversal for this tree:
CPT BinaryTree LettersEx1.svg

Reply:

The potential depth-first traversals are

  • G E B D F Ok M R
  • G E F B D Ok M R
  • G Ok M R E B D F
  • G Ok M R E F B D

The potential breadth-first traversals are

  • G E Ok B F M D R
  • G E Ok F B M D R
  • G Ok E M B F R D
  • G Ok E M F B R D
  • Depth First traversal typically makes use of a Stack
  • Breadth First typically makes use of a Queue

Pre-order[edit]

Binary timber are normally traversed from left to proper, however right-to-left traversal can also be potential and would possibly seem within the examination questions. We’ll due to this fact make the route at all times clear in the remainder of this chapter.

If every node is visited earlier than each of its subtrees, then it is referred to as a pre-order traversal.
The algorithm for left-to-right pre-order traversal is:

  1. Go to the basis node (typically output it)
  2. Do a pre-order traversal of the left subtree
  3. Do a pre-order traversal of the appropriate subtree

which will be carried out as follows, utilizing the tree knowledge construction outlined within the earlier unit:

sub PreOrder(TreeNode)
   Output(TreeNode.worth)
   If LeftPointer(TreeNode) != NULL Then
      PreOrder(TreeNode.LeftNode)
   If RightPointer(TreeNode) != NULL Then
      PreOrder(TreeNode.RightNode)
finish sub

Because the algorithm utterly determines the order by which nodes are visited, there is just one potential left-to-right pre-order traversal for every binary tree. For our instance tree, which is a binary tree, it is F B A D C E G I H.

As a result of a pre-order traversal at all times goes down one department (left or proper) earlier than shifting on to the opposite department, a pre-order traversal is at all times one of many potential depth-first traversals.

Put up-order[edit]

If every node is visited after its subtrees, then it is a submit-order traversal. The algorithm for left-to-right post-order traversal is:

  1. Do a post-order traversal of the left subtree
  2. Do a post-order traversal of the appropriate subtree
  3. Go to the basis node (typically output this)

which will be carried out as:

sub PostOrder(TreeNode)
   If LeftPointer(TreeNode) != NULL Then
      PostOrder(TreeNode.LeftNode)
   If RightPointer(TreeNode) != NULL Then
      PostOrder(TreeNode.RightNode)
   Output(TreeNode.worth)
finish sub

There is just one left-to-right post-order traversal for every binary tree. For our instance tree, it is A C E D B H I G F.

In-order[edit]

If every node is visited between visiting its left and proper subtrees, then it is an in-order traversal. The algorithm for left-to-right in-order traversal is:

  1. Do an in-order traversal of the left subtree
  2. Go to root node (typically output this)
  3. Do an in-order traversal of the appropriate subtree

which will be carried out as:

sub InOrder(TreeNode)
   If LeftPointer(TreeNode) != NULL Then
      InOrder(TreeNode.LeftNode)
   Output(TreeNode.worth)
   If RightPointer(TreeNode) != NULL Then
      InOrder(TreeNode.RightNode)
finish sub

There is just one left-to-right in-order traversal for every binary tree. For our instance tree, it is A B C D E F G H I. Word the nodes are visited in ascending order. That is no coincidence.

In binary search timber like our instance tree, the values within the left subtree are smaller than the basis and the values in the appropriate subtree are bigger than the basis, so a left-to-right in-order traversal visits the nodes in ascending order.

Train: In-order Traversal

Is the assertion “an in-order traversal at all times visits the nodes in ascending order” true or false?

Reply:

It’s false. An in-order traversal solely visits the nodes in ascending order if it is a left-to-right traversal and the tree is a binary search tree.

How would you alter the algorithm above to go to the nodes of a binary search tree in descending order ?

Reply:

A right-to-left in-order traversal would produce the specified order:

  1. Do an in-order traversal of the appropriate subtree
  2. Go to root node (typically output this)
  3. Do an in-order traversal of the left subtree

Traversal Ideas[edit]

Within the examination, you might be given some traversal pseudo-code and a binary tree, and requested to listing the nodes within the order the code will go to them.

The very first thing is to look fastidiously on the code and examine:

  • is the node visited earlier than (pre-order), between (in-order) or after (post-order) visiting the subtrees?
  • is the left subtree visited earlier than the appropriate subtree or the opposite method spherical?

For instance, the next code does a left-to-right traversal and the feedback present the place the go to of the basis would possibly happen.

sub Traversal(TreeNode)
   'Output(TreeNode.worth) REM Pre-Order
   If LeftPointer(TreeNode) != NULL Then
      Traversal(TreeNode.LeftNode)
   'Output(TreeNode.worth) REM In-Order
   If RightPointer(TreeNode) != NULL Then
      Traversal(TreeNode.RightNode)
   'Output(TreeNode.worth)  REM Put up-Order
finish sub

Let’s assume it is left-to-right traversal. As soon as , from the place of the node go to, if it is a pre-, in- or post-order traversal, you possibly can annotate every node of the binary tree as follows:
Sorted binary tree node orders.svg

Kind of Traversal Place of Output code The place to place your mark
Pre High Left
In Center Backside
Put up Backside Proper

Lastly, draw a line going anticlockwise across the tree, connecting the marks. Observe the road and write down every node as you meet a mark: that would be the order by which the code will go to the nodes. Listed below are the three potential left-to-right traversals:

As you possibly can see, following this tip you get hold of the identical solutions as within the sections above.

If the traversal is correct to left, it’s important to draw a clockwise line and swap the place of the pre-order or post-order mark.

Kind of Traversal Place of Output code Mark for left-to-right traversal Mark for right-to-left traversal
Pre High Left Proper
In Center Backside Backside
Put up Backside Proper Left

If the tree is a binary search tree and also you’re requested for an in-order traversal, you need to have visited the nodes in ascending order (for left-to-right traversal) or descending order (for right-to-left traversal). If it isn’t a binary search tree, the in-order traversal will not go to the nodes in neither ascending nor descending order, however a pre-order or post-order traversal would possibly, it is going to all rely the place the nodes are positioned within the tree.

Though on this chapter now we have at all times made specific whether or not it was a left-to-right or right-to-left traversal for readability, the everyday utilization of the phrases pre-order, in-order and post-order implies a left-to-right traversal, if nothing on the contrary is claimed.

Train: Binary Tree Traversal

For the next binary tree carry out a pre-order, an in-order and a post-order traversal.
CPT BinaryTree LettersEx1.svg

Reply:

When nothing else is claimed, a left-to-right traversal is assumed.

  • Pre-order traversal: GEBDFKMR
  • In-order traversal: BDEFGKMR
  • Put up-order traversal: DBFERMKG

What traversal does the next code describe:

sub Traverse(TreeNode)
   If LeftPointer(TreeNode) != NULL Then
      Traverse(TreeNode.LeftNode)
   Output(TreeNode.worth)
   If RightPointer(TreeNode) != NULL Then
      Traverse(TreeNode.RightNode)
finish sub

Reply:

An in-order traversal, as a result of the node go to is within the centre of the code and the left subtree is traversed earlier than the appropriate subtree.

What does the next code do?

sub P(TreeNode)
   If RightPointer(TreeNode) != NULL Then
      P(TreeNode.RightNode)
   If LeftPointer(TreeNode) != NULL Then
      P(TreeNode.LeftNode)
   Output(TreeNode.worth)
finish sub

Reply:

It does a right-to-left post-order traversal, as a result of it first visits the appropriate subtree, then the left subtree and eventually the node.

Utilizing the next binary tree:
CPT BinaryTree NumberEx2(unordered).svg
what can be the outputs for right-to-left:

  • Pre-order traversal
  • In-order traversal
  • Put up-order traversal

Reply:

  • right-to-left pre-order traversal: 7 Eight 1 9 5 three Four 2
  • right-to-left in-order traversal: 1 Eight 9 7 three 5 2 4
  • right-to-left post-order traversal: 1 9 Eight three 2 Four 5 7

Author: admin

Leave a Reply

Your email address will not be published. Required fields are marked *