Win a copy of Mastering Corda: Blockchain for Java Developers this week in the Cloud/Virtualization forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Bear Bibeault
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Jj Roberts
• Carey Brown
Bartenders:
• salvin francis
• Frits Walraven
• Piet Souris

# How recursion actually works

Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:
This question is:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

One example is with this input array, [-10,-3,0,5,9]   , a valid tree would be
0
/   \
-10  5
\    \
-3.   9

This is the code that solves this problem:

I am confused how this exactly works. The output with the above example is [0,-10,5,null,-3,null,9].

I am confused on what each step of recursion does here and when left would ever be greater than right? Could someone walk through the steps on what the left, right, and midpoint would be at each step of this function? I am confused at which points the right recursive call is used after the left.

I haven't been able to fully understand recursion and this would help a ton!
Thank you so much any help is appreciated.

Saloon Keeper
Posts: 12608
273
• Number of slices to send:
Optional 'thank-you' note:
buildTree() takes a subrange of a vector and splits it in three parts: A middle element, and the elements left of the middle and the elements right of the middle.

The middle element is used to create the root of the tree, and the left elements and right elements are used to create the left and right subtrees respectively.

At some point, you can no longer split the vector up in three parts anymore, right? For instance, what happens when the subrange of the vector only contains one element?

For instance, let's say that left is 4 and right is also 4. This corresponds to the sub-vector [9]. The mid variable will then be 4 + (4 - 4) / 2 which evaluates to 4. So the root of the corresponding subtree is nums[4], or 9. Here are how the subtrees of the subtree with root 9 are built:

In both subtrees, left > right. That means that the subtree with root 9 looks like this:

9
/ \
null null

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?