Insert Node in a Binary Search Tree

Problem

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

Example

Given binary search tree as follow, after Insert node 6, the tree should be:

      2             2
     / \           / \
    1   4   -->   1   4
       /             / \
      3             3   6

Challenge

Can you do it without recursion?