! javascript tree traversal.md

JavaScript Tree Traversal

• Tree Node
• traverseTreeInOrder
• traverseTreePostOrder
• traverseTreePreOrder
• depthFirstSearch

depthFirstSearch.js

function depthFirstSearch(node, target)
{
    if (!node) return null;
    if (node.value === target)
        return node;
    
    const left = depthFirstSearch(node.left, target);
    if (left != null)
        return left;

    const right = depthFirstSearch(node.right, target);
    return right;
}

traverseBreadthFirst

function traverseBreadthFirst(node, visit)
{
    const queue = [node];

    let curr = node;
    while(queue.length > 0)
    {
        curr = queue.shift();
        visit(curr.val);
        
        if (curr.left) {
            queue.push(curr.left)
        }
        if (curr.right) {
            queue.push(curr.right)
        }
    }
}

traverseTreeInOrder.js

function traverseTreeInOrder(node, handler)
{
    if (node == null) {
        return;
    }
    traverseTreeInOrder(node.left, handler);
    handler(node.value, node);
    traverseTreeInOrder(node.right, handler);
}

function traverseTreeInOrderS(node, visit)
{
    const stack = [];

    let curr = node;
    while(curr || stack.length > 0)
    {
        while (curr)
        {
            stack.push(curr);
            curr = curr.left;
        }
        
        curr = stack.pop();
        visit(curr.value, curr);
        
        curr = curr.right;
    }
}

traverseTreePostOrder.js

function traverseTreePostOrder(node, handler)
{
    if (node == null) {
        return;
    }
    traverseTreeInOrder(node.left, handler);
    traverseTreeInOrder(node.right, handler);
    handler(node.value, node);
}

traverseTreePreOrder.js

function traverseTreePreOrder(node, handler) {
    if (node == null) {
        return;
    }
    handler(node.value, node);
    traverseTreeInOrder(node.left, handler);
    traverseTreeInOrder(node.right, handler);
}

TreeLoader.js

class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    print(indent)
    {
        indent = indent || 0;
        console.log(`${'  '.repeat(indent)} + ${this.val}`);
        if (this.left)
            this.left.print(indent + 1);
        if (this.right)
            this.right.print(indent + 1);        
    }
}

function parseTree(str)
{
  const parts = str == "" ? [] : str.split(' ');
  
  function buildTree(nodes) {
      const val = nodes.next().value;
      if (val === 'x') return null;
      const left = buildTree(nodes);
      const right = buildTree(nodes);
      return new Node(parseInt(val), left, right);
  }
  
  return buildTree(parts[Symbol.iterator]());
}

parseTree("8 5 2 x 3 x x 6 x x 10 x 14 x x").print();

parseTree("421 223 79 42 x x 157 133 x x x 327 x 404 356 x x 415 x x 741 626 x x 887 801 795 x x 842 x x 903 x 977 x x").print();