Binary Tree Representation in Java
EasyA node class with two references
Problem
Represent a binary tree with a Node class holding a value and left/right references, and build one in code.
Each node is a box holding a value and two arrows to its left and right child.
The idea
A node stores its value plus references to its children, and null marks the absence of a subtree. Because the tree is reached entirely through the root, losing the root loses the tree.
The trick
- null children are the base case, not a special sentinel object.
- A complete tree can also live in an array, with children at 2i+1 and 2i+2.
Step 1 of 8. Inorder = Left → Node → Right. We dive left first, emit the node, then go right.
1/8
Optimal
timeO(n)spaceO(h)
Order = when you emit the node.
1function inorder(node) {2 if (!node) return;3 inorder(node.left);4 visit(node.val); // node between children5 inorder(node.right);6}Input
- nodes
- 6, 5 edges
Output
- output
- —
- inorder
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- Node(1); left=Node(2); right=Node(3)
- Output:
- tree of 3 nodes
Finished the walkthrough? Add it to your streak.