Binary Search Trees (II)

Computer Science Level 3

Let m i n min and m a x max be the m i n i m u m minimum and the m a x i m u m maximum number of nodes in a BST (Binary Search Tree) of length (or height) 3 respectively. Find the value of m i n + m a x min+max

Details and Assumptions:

  • R o o t Root n o d e node is considered to be at height ZERO.


The answer is 19.

Zeeshan Ali by Zeeshan Ali , 25, Pakistan

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Zeeshan Ali
Jan 16, 2016

A BST of height h h is a two-way tree, which means it has some nodes such that each node has at most two children or no child. Hence m i n = h + 1 min=h+1 and m a x = 2 h + 1 − 1 max=2^{h+1}-1 . Therefore a BST of height 3 has minimum 4 4 and maximum 2 3 + 1 − 1 = 2 4 − 1 = 16 − 1 = 15 2^{3+1}-1=2^4-1= 16-1=15 nodes. Hence m i n + m a x = 4 + 15 = 19 min+max=4+15=\boxed{19}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Please make it clear how is a tree with a single node has height 3.?

Aravind Vishnu - 5 years, 1 month ago

Log in to reply

Yeah! You are right.. I have edited my solution and reported the problem to get the answer changed to 19..

Zeeshan Ali - 5 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...