How to use recursion function to traverse tree in Javascript

Question

I was building a tree traverse function and it has to use recursion.

What I want the output to be is

'{"value":9,"left":{"value":4,"left":{"value":1},"right":{"value":6}},"right":{"value":20,"left":{"value":15},"right":{"value":170}}}'

Could someone figure out how to use recursion in the traverse function to get the output?

Here is my JS:

   
    class Node {
       constructor(value){
       this.left = null;
       this.right = null;
       this.value = value;
      }
     }

    class BinarySearchTree {
         constructor(){
         this.root = null;
     }
    insert(value){
        const newNode = new Node(value);
    if (this.root === null) {
        this.root = newNode;
    } else {
        let currentNode = this.root;
        while(true){
        if(value < currentNode.value){
          //Left
          if(!currentNode.left){
            currentNode.left = newNode;
            return this;
          }
          currentNode = currentNode.left;
        } else {
          //Right
          if(!currentNode.right){
            currentNode.right = newNode;
            return this;
          } 
          currentNode = currentNode.right;
          }
         }
        }
       }  
      }

     const tree = new BinarySearchTree();
     tree.insert(9)
     tree.insert(4)
     tree.insert(6)
     tree.insert(20)
     tree.insert(170)
     tree.insert(15)
     tree.insert(1)
     JSON.stringify(traverse(tree.root))

    //     9
   //  4     20
   //1  6  15  170

  function traverse(node) {
      const tree = { value: node.value };
      tree.left=node.left
       if(node.left===null) {
            return  null
      }else{
           traverse(node.left);
      }     
      tree.right=node.right
          if(node.right===null) {
                 return null
          }else{
                 traverse(node.right);
            }
       }

Answer 1

You're on the right track; I see that you need specially-formatted objects in your result string. I recommend starting by checking whether the current node is null; if so, return nothing (this key will be ignored by the calling function). Otherwise, create a node object to prepare for return and traverse left and right children. After traversing both subtrees recursively, return the root node. This will build the result structure up from the leaves and end with the root.

In your code,

   if(node.left===null) {
        return  null

is a bit premature, for example. If node has a right subtree, we don't want to abandon traversing it. It's also necessary to return something to the caller in all cases except for empty children.

Also, you may consider putting traverse in the BinaryTree class and have it operate on its member field; I left it as-is in the below example.

Lastly, this is a pre-order traversal; visit the root first, then the left and right subtrees.

function traverse(node) {
  if (node) {
    const left = traverse(node.left);
    const right = traverse(node.right);    
    return {
      value: node.value,
      [left&&"left"]: left,
      [right&&"right"]: right
    };
  }
}

class Node {
  constructor(value, left=null, right=null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  insert(value) {
    const newNode = new Node(value);
    
    if (this.root === null) {
      this.root = newNode;
    } 
    else {
      let currentNode = this.root;
      
      while (true) {
        if (value < currentNode.value) {
          if (!currentNode.left) {
            currentNode.left = newNode;
            return this;
          }
          
          currentNode = currentNode.left;
        } 
        else {
          if (!currentNode.right) {
            currentNode.right = newNode;
            return this;
          }
          
          currentNode = currentNode.right;
        }
      }
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
console.log(JSON.stringify(traverse(tree.root)));
console.log(traverse(tree.root));

//      9
//   4     20
// 1  6  15  170