Win a copy of Mastering Corda: Blockchain for Java Developers this week in the Cloud/Virtualization forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
reply
    Bookmark Topic Watch Topic
  • New Topic