title: Why is the recursive insertion method of the BST not working
body: <p>I wrote the following code to implement the recursive insert method for the BST. But when I print the tree in walk over order it prints the original tree before insertion. It seems as if the element was not inserted. Please help me out. Thanks in advance. Also please suggest the change in code. By the way, the intial tree in walk over order is 2 5 5 6 7 8.</p>
  
  <pre><code>package DataStructures;
  
  class TreeNode {
      private TreeNode parent;
      private TreeNode childLeft;
      private TreeNode childRight;
      private int key;
  
      public TreeNode(){
  
      }
  
      public TreeNode(int key) {
          this(key, null);
      }
  
      public TreeNode(int key, TreeNode parent) {
          this(key, parent, null, null);
      }
  
      public TreeNode(int key, TreeNode parent, TreeNode childLeft, TreeNode childRight) {
          this.key = key;
          this.parent = parent;
          this.childLeft = childLeft;
          this.childRight = childRight;
      }
  
      public int getKey() {
          return key;
      }
  
      public void setKey(int key) {
          this.key = key;
      }
  
      public TreeNode getParent() {
          return parent;
      }
  
      public void setParent(TreeNode parent) {
          this.parent = parent;
      }
  
      public TreeNode getChildLeft() {
          return childLeft;
      }
  
      public void setChildLeft(TreeNode childLeft) {
          this.childLeft = childLeft;
      }
  
      public TreeNode getChildRight() {
          return childRight;
      }
  
      public void setChildRight(TreeNode childRight) {
          this.childRight = childRight;
      }
  }
  
  public class BinarySearchTreeBasicTest {
      private static class BinarySearchTree {
          private TreeNode root;
          private TreeNode maxNode = new TreeNode(0);
  
          public BinarySearchTree(TreeNode root) {
              this.root = root;
          }
  
          public void printTheTreeInOrderWalk(TreeNode x) {
              if (x != null) {
                  printTheTreeInOrderWalk(x.getChildLeft());
                  System.out.print(x.getKey() + " ");
                  printTheTreeInOrderWalk(x.getChildRight());
              }
          }
  
  
  
  
  
  
  
  
  
          public void insertNode(TreeNode node, int key){
              if (node == null){
                  node = new TreeNode(key);
              }
              else{
                  if (node.getKey() &gt; key){
                      insertNode(node.getChildLeft(), key);
                  } else if (node.getKey() &lt; key){
                      System.out.println("k");
                      insertNode(node.getChildRight(), key);
                  } else{
                      // dont do anything
                  }
              }
          }
      }
  
      public static void main(String[] args) {
          TreeNode rootNode = new TreeNode(6);
          BinarySearchTree tree = new BinarySearchTree(rootNode);
          TreeNode node1 = new TreeNode(5);
          TreeNode node2 = new TreeNode(7);
          rootNode.setChildLeft(node1);
          rootNode.setChildRight(node2);
          node1.setParent(rootNode);
          node2.setParent(rootNode);
          TreeNode node3 = new TreeNode(2);
          TreeNode node4 = new TreeNode(5);
          node1.setChildLeft(node3);
          node1.setChildRight(node4);
          node3.setParent(node1);
          node4.setParent(node1);
          TreeNode node5 = new TreeNode(8);
          node5.setParent(node2);
          node2.setChildRight(node5);
          tree.insertNode(rootNode, 3);
          tree.printTheTreeInOrderWalk(rootNode);
      }
  }
  </code></pre>