7.Depth First & Tree Traversals

1. Depth-First Traversal

• Downward through the tree

• DFS algorithm is required to a stack

2. DFS 구현

기본 코드

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

const a = new Node("a");
const b = new Node("b");
const c = new Node("c");
const d = new Node("d");
const e = new Node("e");
const f = new Node("f");

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

const depthFirstPrint = (root) => {
  const stack = [ root ];
  while(stack.length > 0) {
    const curr = stack.pop();
    console.log(curr.val);

    if(curr.right !== null) {
      stack.push(curr.right);
    }

    if(curr.left !== null) {
      stack.push(curr.left);
    }
  }
}; // O(n) time, O(n) space;

console.log(depthFirstPrint(a));

재귀 적용

... 

const depthFirstPrint = (root) => {
  if (root === null) return;

  console.log(root.val);
  depthFirstPrint(root.left);
  depthFirstPrint(root.right);
}; // O(n) time, O(n) space;

console.log(depthFirstPrint(a)); // abdcf

Post order

• left노드 -> right노드 -> self노드

...
const postOrder = (root) => {
  if (root === null) return;

  postOrder(root.left);
  postOrder(root.right);
  console.log(root.val);
}; // O(n) time, O(n) space;

console.log(postOrder(a)); // debfca

in-order order

• left노드 -> self노드 -> right노드

...
const inOrder = (root) => {
  if (root === null) return;

  inOrder(root.left);
  console.log(root.val);
  inOrder(root.right);
  
}; // O(n) time, O(n) space;

console.log(inOrder(a)); // debacf

3. DFS Sum Tree 구현

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

const a = new Node(1);
const b = new Node(2);
const c = new Node(3);
const d = new Node(4);
const e = new Node(5);
const f = new Node(6);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

const sumTree = (root) => {
  let sum = 0;
  const stack = [ root ];
  while(stack.length > 0) {
    const curr = stack.pop();
    
    sum += curr.val;

    if(curr.right !== null) {
      stack.push(curr.right);
    }

    if(curr.left !== null) {
      stack.push(curr.left);
    }
  }

  return sum;
};

console.log(sumTree(a));

재귀 구현

...

const sumTree = (root) => {
  if (root === null) return 0;

  return sumTree(root.left) + root.val + sumTree(root.right);
};

console.log(sumTree(a));

참고: codebyte - Depth First & Tree Traversals