CODEWITHSUNDEEP
algorithmdata-structuresassemblybinary-treebinary-search-tree
Salih Erikci
Salih Erikci

Reputation: 5087

How to print a Binary Search Tree?

hi i have implemented a bst in mips and i need to print this tree. Each node has following four information

i should print the tree in the following format. (x means no child)

12

8-16

x-9  13-17

x-x  x-11 x-x  x-x

Could you please suggest a way to implement this print method?

Upvotes: 1

Views: 1572

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

The ordering in which you are printing the tree is a breadth-first (level-by-level) traversal. One option would be as follows: maintain a work list, initially seeded with the root of the tree. Then, repeatedly dequeue from the work list, print the current element (or x if none is present), then add the two children to the work list. You would need some way to track when you're done traversing the tree, perhaps by counting the number of nodes first and stopping once you've printed that many nodes.

That said, since you're doing this in MIPS, one simpler option is to linearize the tree into an array, then print the array. If you number the nodes in a fashion similar to how you number the nodes in an implicit binary heap, you can recursively/iteratively walk the tree, fill in the array with the tree nodes, then walk over the array printing everything out.

Hope this helps!

Upvotes: 1

Michael
Michael

Reputation: 11

As you need to print level by level of your binary tree, the most obivous way to print the information is to traverse the tree using breadth-first search method. The rest is straightforward and shouldn't be a problem. :)

Upvotes: 1

Related Questions