Tree algorithms in Scala: DFS, BFS and Height of binary tree

Tree:

         3
   5          2
1   4      6

Preorder Traversal

root -> left subtree -> right subtree
3 ->  5 -> 1 -> 4 -> 2 -> 6

def preOrder(node: Node): Unit = {
  if (node != null){
    print(node.value + " ")
    preOrder(node.left)
    preOrder(node.right)
  }
}

def iterativePreOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  while (stack.nonEmpty || node != null) {
    if (node != null) {
      print(node.value + " ")
      if (node.right != null) stack.push(node.right)
      node = node.left
    }
    else {
      node = stack.pop()
    }
  }
}

InOrder Traversal

left subtree -> root -> right subtree
1 -> 5 -> 4 -> 3 -> 6 -> 2

def inOrder(node: Node): Unit = {
  if (node != null){
    inOrder(node.left)
    print(node.value + " ")
    inOrder(node.right)
  }
}

def iterativeInOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  while (stack.nonEmpty || node != null) {    if (node != null) {      stack.push(node)      node = node.left    }    else {      node = stack.pop()      print(node.value + " ")      node = node.right    }  }
}

PostOrder Traversal

left subtree -> right subtree -> root
1 -> 4 -> 5 -> 6 -> 2 -> 3

def postOrder(node: Node): Unit = {
  if (node != null) {
    postOrder(node.left)
    postOrder(node.right)
    print(node.value + " ")
  }
}

def iterativePostOrder(root: Node): Unit = {
  val stack = new mutable.Stack[Node]()
  var node = root
  var prev: Node = null  while (stack.nonEmpty || node != null) {
    if (node != null) {
      stack.push(node)
      node = node.left
    }
    else {
      node = stack.pop()
      if (node.right != null && prev != node.right) {
        stack.push(node)
        node = node.right
      }
      else {
        print(node.value + " ")
        prev = node
        node = null      }
    }
  }
}

Breadth first search

3 -> 5 -> 2 -> 1 -> 4 -> 6 

def bfs(root: Node): Unit = {
  val q = new mutable.Queue[Node]()
  var node = root

  q.enqueue(node)
  while (q.nonEmpty) {
    node = q.dequeue()
    print(node.value + " ")
    if (node.left != null) q.enqueue(node.left)
    if (node.right != null) q.enqueue(node.right)
  }
}

Height of a binary tree

def height(root: Node): Int = {
  val q = new mutable.Queue[(Node, Int)]()
  var node = root

  q.enqueue((node, 1))
  var max = 1  while (q.nonEmpty) {
    val d = q.dequeue()
    node = d._1

    if (node.left != null) {
      max = d._2 +1      q.enqueue((node.left, max))
    }
    if (node.right != null) {
      max = d._2 +1      q.enqueue((node.right, max))
    }
  }
  max
}