C++, How to create and draw a Binary Tree then traverse it in Pre-Order

Question

How do I create a Binary Tree and draw it using a Pre-Order Traversal strategy? The root would be the first number going in.

I have a set of numbers: 48 32 51 54 31 24 39. 48 would be the root. How are the child nodes pushed onto the Binary Tree in a Pre-Order traversal?

Are you trying to construct a binary tree given a pre-order traversal? Or are you trying to get the pre-order travel on a binary tree? (sorry, the question is not very clear) — Aamir
– Aamir, Commented Dec 9, 2012 at 22:39
what are the numbers that would result from a PRe-Order Traversal of the binary tree built using the above numberrs — Ryan
– Ryan, Commented Dec 10, 2012 at 1:08

Shahbaz · Accepted Answer · 2012-12-09 22:43:13Z

2

Imagine the following sub-problem. You have a set of numbers:

N A1...AX B1...BY

You know that N is the root of the corresponding tree. All you need to know is what numbers form the left sub-tree. Obviously the rest of the numbers form the right sub-tree.

If you remember the properties of a binary-search trees, you would know that elements of the left sub-tree have values smaller than the root (while the ones on the right have values bigger).

Therefore, the left sub-tree is the sequence of numbers that are smaller than (or possibly equal to) N. The rest of the numbers are in the right sub-tree.

Recursively solve for

A1...AX

and

B1...BY

For example given:

10 1 5 2 9 3 1 6 4 11 15 12 19 20

You get:

root: 10
left sub-tree: 1 5 2 9 3 1 6 4
right sub-tree: 11 15 12 19 20

answered Dec 9, 2012 at 22:43

Shahbaz

47.8k19 gold badges120 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ryan Over a year ago

Ok, maybe it's just me but I can't pinpoint this. Ill give you an array of intergers: 47 43 20 24 32 44 35. So the tree would be: 47 left sub-tree: 20 24 32 right sub-tree: 44,43,35?

Shahbaz Over a year ago

No, 44, 43 and 35 are all smaller than 47. This means that 47 is the root, left sub-tree contains all the 6 numbers and the right sub-tree is empty.

Community · Accepted Answer · 2017-05-23 12:21:19Z

2

Say you have the following binary tree:

        A
      /    \  
    B        C   
   / \      / \
  D   E    F   G
     / \    
    H   I

A Pre-Order Traversal goes NODE, LEFT, RIGHT.

So Pre-Order of this binary tree would be: A B D E H I C F G

For more details on how to implement this in C++: https://stackoverflow.com/a/17658699/445131

edited May 23, 2017 at 12:21

CommunityBot

11 silver badge

answered Dec 9, 2012 at 23:07

NoxSatuKeir

272 bronze badges

Collectives™ on Stack Overflow

C++, How to create and draw a Binary Tree then traverse it in Pre-Order

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related