CODEWITHSUNDEEP
data-structures
Xianyi Ye
Xianyi Ye

Reputation: 1043

Does an balanced binary tree has an unique form?

Does an balanced binary tree has an unique form? For example, the node list [1,2,3,4,5]

It seems like following two forms are all qualified with the definition of balanced binary tree. Are they all correct?

    2
   / \ 
  1   4
     / \
    3   5

    3
   / \
  1   4
   \   \
    2   5

Upvotes: 1

Views: 2433

Answers (3)

Muhammad Yaseen Khan
Muhammad Yaseen Khan

Reputation: 809

With AVL (self-balancing binary tree) you will yield a unique form; provided you have same sequence of data, that in your case is [1,2,3,4,5].

   2
   / \ 
  1   4
     / \
    3   5

Upvotes: 2

amit
amit

Reputation: 178451

No. There isn't. A balanced tree may have different order based on the order of operations made in order to get to it. Also, there are multiple ways to do a self balancing tree (Red-Black, AVL, Splay) - all result (usually) in different trees.

A simple counter example with two nodes on AVL tree:

insert(1)
insert(2)

Will result in no need for rebalancing, and the tree will be:

1
 \
  \
   2

If you do it the other way around:

insert(2)
insert(1)

Again, no rebalancing is needed, but the result tree will be:

     2
   /
  /
 1

Both are valid AVL trees with the same elements, but as you can see - the form is not unique.

Upvotes: 4

ravi
ravi

Reputation: 10733

The structure of balanced binary search tree OR for that matter binary search tree is much dependent on the sequence of data you provide to it.

Upvotes: 2

Related Questions