Binary Search Tree Inorder Search Question

Greetings. I just finished the challenge Use Depth First Search in a Binary Search Tree.

This post contains a spoiler since it has the answer.
So this is the FCC answer to the inorder search and it’s waaay simpler than what I did:

this.inorder = function() {
    if (this.root === null) return null;
    const nodes = [];
    function traverse(root) {
      if (root === null) return;
      traverse(root.left);    // Left
      nodes.push(root.value); // Root (in-order)
      traverse(root.right);   // Right
    }
    traverse(this.root);
    return nodes;
  }

Would someone please explain to me how it ever gets past the leftmost item in the tree? From what I understand, return simply ends the function (where it says if (root === null) return;).
How does traverse run again at that point if it isn’t called again? And how does it ever get to the right side, and how does it avoid pushing duplicate values onto the nodes array over and over?

Thank you for your help. There’s always so much to learn.

Thing that needs to be kept in mind here is that each node can be considered as a sub-tree. It’s tree within a tree, within a tree. Trees all the way down really (:slight_smile: ).

traverse functions handles traversing tree by using that property. If passed in root is null, it just returns, meaning there’s no further nodes in this part of tree. However if root isn’t null and it’s another node - another sub-tree, then this part comes to play.

      traverse(root.left);    // Left
      nodes.push(root.value); // Root (in-order)
      traverse(root.right);   // Right

What happens here? Remembering that each node has left and right child (which may or may not be null), traverse is called recursively with left child of the node. For the current node (let’s call it current_node for simplicity) code doesn’t go forward, until all children nodes in the left child are visited.

Let’s assume that happens, without worrying much about the details for now. Function for the current_node can now resume, by pushing value to the nodes array. After that the right child of the current_node - sub-tree is visited recursively. Again continuing deeper into the sub-tree.

Once all children in the sub-tree of the right child of current_node are visited, function for current_node is finished. This is the point, at which, if current_node has parent, that parent now can push it’s value to the nodes and the continue with traversing right child sub-tree. And if the current_node is the this.root, then the nodes array can be returned.

There’s no duplicates in the nodes array, because each node is visited only once. Single node can have only single parent, and two child nodes.

Visualizing how this happens may help with wrapping mind around it. You can try following by hand the process for some small tree or try some tool helping with visualizing execution, for example: https://pythontutor.com/javascript.html

1 Like

Trees all the way, down, lol. Thank you for this helpful response. The website you linked to is super useful! I also found this video incredibly informative: Depth First & Tree Traversals (Pre, In, Post) Explained - YouTube

What helped me from the video was when he said that in the background, when you use recursion, the program treats all the function calls as a stack, and a stack is normally used in a depth-first search anyway so it does a lot of the background work for you.

1 Like