0

I wrote the small class below for playing with a binary tree. Is it possible to do depth first search with out recursion?

It looks like you might need a queue to remember where you are in the traversal, but I'm not sure.

Is there a way to do it with out adding another data structure?

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

class BinaryTree {

  constructor(data) {
    this.root = new Node(data);
    this.makeTree();
  }

  makeTree(){
    this.insert(15);
    this.insert(5);
    this.insert(7);
    this.insert(3);
    this.insert(20);
    this.insert(13);
  }

  insert(data) {
    let iter = this.root;
    let node = new Node(data);
    while(iter) {
      if(iter.left && (node.data < iter.data)){
        iter = iter.left;
      }
      if(!iter.left && (node.data < iter.data)){
        iter.left = node;
        return;
      }
      if(iter.right && (node.data >= iter.data)){
        iter = iter.right;
      }
      if(!iter.right && (node.data >= iter.data)){
        iter.right = node;
        return;
      }
    }
  }

  df() {
    function dfInner (node) {
      if(node === null) {
        return node;
      }

      // pre order
      dfInner(node.left);

      // in order
      dfInner(node.right);

      // post order

    }
    dfInner(this.root);
  }

}

const tree = new BinaryTree(10);
tree.df();
user17331023
  • 51
  • 6
  • 3
    yes, use a stack and simulating the recursion stack. – user1984 Dec 13 '21 at 23:11
  • @user that is what I was thinking ... `const stack = []; stack.push(a)`, what would `a` be, just the node before iterating the next loop? – user17331023 Dec 13 '21 at 23:31
  • @Keith - depth first search is different from binary search. – user17331023 Dec 13 '21 at 23:31
  • Oh, missed that bit.. My bad – Keith Dec 13 '21 at 23:34
  • If you have a ordered binary tree you only need to follow one of the two brachens and thus you can do that with a iterative process, either through tail recursion or perhaps a while loop. A traversal would be impossible without recursion or a stack and both are recursive processes. – Sylwester Dec 14 '21 at 00:58
  • @Sylwester You'd call an iterative stack-using solution recursive, or do I misunderstand you? – Kelly Bundy Dec 14 '21 at 10:33
  • https://stackoverflow.com/questions/33703019/breadth-first-traversal-of-a-tree-in-javascript/33704700#33704700 – Matt Timmermans Dec 14 '21 at 14:27
  • I think you could use the base case `node === null` as a comparator for the while loop. Outside the while loop you could push the root node on to the stack. In the while loop conditional you would also pop the node. This would make the while loop behave like successive function calls. This is interesting on how to correlate while loops to recursion or function call stacks have you. – user17331023 Dec 17 '21 at 23:35
  • Yes, of course, because everything that can be done with recursion can be done with iteration and vice versa. But why would you want to? You have a recursive data structure. The best-fit algorithms to work with it are always going to be recursive. – Scott Sauyet Dec 18 '21 at 22:32

0 Answers0