As a supportive thing for some careercup challenges I wrote a class for a BST Node.
public class Node { Node left; Node right; Node parent; int data; Node(int data, Node parent) { this.data = data; this.parent = parent; } /** * Put an int into left node and return it * @return Node */ protected Node putLeft(int data) { if (this.left == null) { this.left = new Node(data, this); return this.left; } else { return left.put(data); } } /** * Put an int into right node and return it * @return Node */ protected Node putRight(int data) { if (this.right == null) { this.right = new Node(data, this); return this.right; } else { return right.put(data); } } /** * Ask Node to put an int into its children and return it * @return Node */ public Node put(int data) { if (data == this.data) { return this; } else { return data < this.data ? this.putLeft(data) : this.putRight(data); } } @Override public String toString() { // Example: 20 {10, 30} String l = this.left != null ? String.valueOf(left.data) : ""; String r = this.right != null ? String.valueOf(right.data) : ""; String c = ""; if (this.left != null || this.right != null) { c = " {"+ l +", " + r +"}"; } return String.valueOf(this.data) + c; } }
It also stores the reference to the parent Node so you can traverse the tree once you have the Node object
Usage:
Node root = new Node(20, null); root.put(10); root.put(30); root.put(5); System.out.println(root); // 20 {10, 30} System.out.println(root.left); // 10 {5, } System.out.println(root.right.parent); // 20 {10, 30}
I didn’t add getters here to make the code shorter (KISS)