Your calls to insert(root.right/left, d) do not change the original right/left nodes if they are null, but simply make the method arguments point to a new variable (which, as you noticed, in Java won't change the original reference). Your change to the first root works because you call a different method, insert(int).

Have you considered making left and right BinaryTrees instead of Nodes? Also, instead of using "null", consider having an "empty" BinaryTree (with a null root and an isEmpty method).

Note that conceptually, left and right are trees, not nodes, so the design will be cleaner.

Your calls to insert(root.right/left, d) do not change the original right/left nodes if they are null, but simply make the method arguments point to a new variable (which, as you noticed, in Java won't change the original reference). Your change to the first root works because you call a different method, insert(int).

Have you considered making left and right BinaryTrees instead of Nodes? Also, instead of using "null", consider having an "empty" BinaryTree (with a null root and an isEmpty method).

Note that conceptually, left and right are trees, not nodes, so the design will be cleaner.

Example code. Untested but the idea should be right:

class Node { BinaryTree left, right; Integer data; Node(Integer d, BinaryTree left, BinaryTree right) { this.data = d; this.left = left; this.right = right; } } class BinaryTree { Node root; // Empty tree BinaryTree() { this(null); } BinaryTree(Node root) { this.root == root; } void insert(int d) { if (this.root == null) { // The tree was empty, so it creates a new root with empty subtrees this.root = new Node(d, new BinaryTree(), new BinaryTree()); } else if (d > this.root.data) { this.root.right.insert(d); } else if (d < this.root.data) { this.root.left.insert(d); } } } 

Notes:

• I respected the style of your existing code.
• This implementation will skip repeated elements.