CODEWITHSUNDEEP
calgorithm
richard_d_sim
richard_d_sim

Reputation: 913

How would you print a binary tree by it's rows?

I'm new to learning about binary trees. I'm trying to figure out how to print the values of a binary tree by it's rows.

Example:

             .-------(098)-------.
      .--(012)--.         .--(402)--.
   (006)     (056)      (256)     (512)

Will output:

 >98
 >12
 >402
 >6
 >56
 >256
 >512

Assume that you are given the root node. Thanks for taking the time to help.

Upvotes: 0

Views: 1081

Answers (1)

Sumeet
Sumeet

Reputation: 8292

Basically a BFS (breadth first search) will do the required. Its other name is level-order-traversal. The reason why it is called level order traversal is because it traverses the tree level by level.

For example in case of your binary tree, the levels are:

           .-------(098)-------.                  //level 0
      .--(012)--.         .--(402)--.             //level 1
   (006)     (056)      (256)     (512)           //level 2

The other convention is that level starts from 1. Now because BFS traverses the tree level by level

First 098 is visited and we are done with level 0

Then 012 and 402 is visited and we are done with level 1

Then 006 , 056 , 256 , 512 are visited and we are done with level 2

BFS is not only meant for binary trees, its basically a graph traversal algorithm, and because a tree is nothing but a graph that is connected with no cycle, we can use it for tree as well.

Depending on the data structure used the time and space complexity varies:

If adjacency matrix is used to represent the graph then:

Time complexity: O(V^2) and Space complexity : O(V^2)

If adjacency list is used to represent the graph then:

Time complexity: O(V + E) and Space complexity : O(V + E)

Following is BFS pseudocode that can be easily converted to code:

BFS(source vertex v)
{
 Enque(v)
 Mark v as visited.
 While(Q is not empty)
  {
    Vertex v’ = deque(Q)
    For all adjacent vertices of v’ that are not visited
     {  Enque them and mark them as visited  }
    We are done with vertex v’
  }
}

Upvotes: 3

Related Questions