0

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?

Eric Leschinski
  • 146,994
  • 96
  • 417
  • 335
Ryan
  • 11
  • 1
  • 2
    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 Dec 09 '12 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 Dec 10 '12 at 01:08

2 Answers2

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
Shahbaz
  • 46,337
  • 19
  • 116
  • 182
  • 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? – Ryan Dec 10 '12 at 01:16
  • 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. – Shahbaz Dec 10 '12 at 12:37
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

Community
  • 1
  • 1
NoxSatuKeir
  • 27
  • 2