Binary Tree Representation (Java)
Description
You are given an array nodes containing 7 integers. These integers represent the values of nodes of a binary tree arranged in level order traversal — that is, the first element is the root, the next two are the children of the root (left then right), the next four are the children of those nodes (again left to right), and so on.
You are also given a root node whose value is already set to nodes[0].
Your task is to construct the complete binary tree by creating the remaining 6 nodes and connecting them to the appropriate parent nodes so that the resulting tree matches the level order arrangement of the input array.
Examples
Example 1
Input: nodes = [1, 2, 3, 4, 5, 6, 7]
Output:
1
/ \
2 3
/ \ / \
4 5 6 7
Explanation: The root node has value 1 (index 0). Its left child is 2 (index 1) and right child is 3 (index 2). Node 2's left child is 4 (index 3) and right child is 5 (index 4). Node 3's left child is 6 (index 5) and right child is 7 (index 6). All 7 elements of the array are placed into the tree following the level order pattern.
Example 2
Input: nodes = [10, 20, 30, 40, 50, 60, 70]
Output:
10
/ \
20 30
/ \ / \
40 50 60 70
Explanation: The root is 10. Following level order, 20 becomes the left child of 10, and 30 becomes the right child. Then 40 and 50 become the children of 20, while 60 and 70 become the children of 30. The tree has 3 levels with all positions filled — a complete binary tree.
Example 3
Input: nodes = [5, 5, 5, 5, 5, 5, 5]
Output:
5
/ \
5 5
/ \ / \
5 5 5 5
Explanation: Even when all values are the same, the tree structure remains identical — a complete binary tree with 3 levels. Each node is created with value 5, and the parent-child relationships are determined purely by position in the array, not by the values themselves.
Constraints
- nodes.length = 7
- 1 ≤ nodes[i] ≤ 100
Editorial
Brute Force
Intuition
The most straightforward way to build this tree is to directly and manually create each node and wire it to the correct parent. Since we know the array always has exactly 7 elements, we know the exact shape of the tree: 3 levels, fully filled. There is no ambiguity about which node goes where.
Think of it like assembling a small piece of furniture with numbered parts and a fixed diagram. Part 1 is the top piece (root). Part 2 attaches to the left of Part 1. Part 3 attaches to the right of Part 1. Part 4 attaches to the left of Part 2, and so on. You simply follow the blueprint, connecting each piece one by one.
We already have the root node (value = nodes[0]). We just need to:
- Create a node for nodes[1] and attach it as root's left child
- Create a node for nodes[2] and attach it as root's right child
- Create nodes for nodes[3] and nodes[4] and attach them as children of node[1]
- Create nodes for nodes[5] and nodes[6] and attach them as children of node[2]
Step-by-Step Explanation
Let's trace through with nodes = [1, 2, 3, 4, 5, 6, 7]:
Step 1: The root node already exists with value 1 (nodes[0]). The tree currently has just one node.
Step 2: Create a new node with value 2 (nodes[1]). Attach it as the left child of the root. Now root has a left child.
Step 3: Create a new node with value 3 (nodes[2]). Attach it as the right child of the root. Now root has both children — level 1 is complete.
Step 4: Create a new node with value 4 (nodes[3]). Attach it as the left child of node 2 (root's left child). This starts filling level 2.
Step 5: Create a new node with value 5 (nodes[4]). Attach it as the right child of node 2. Node 2 now has both its children.
Step 6: Create a new node with value 6 (nodes[5]). Attach it as the left child of node 3 (root's right child).
Step 7: Create a new node with value 7 (nodes[6]). Attach it as the right child of node 3. Node 3 now has both its children.
Result: All 7 nodes are created and connected. The complete binary tree with 3 levels is built.
Direct Manual Assignment — Building the Tree Node by Node — Watch how each node from the array is manually created and attached to its parent, building the complete binary tree one connection at a time.
Algorithm
- The root node already exists with value nodes[0]
- Create a new node with value nodes[1] and set it as root's left child
- Create a new node with value nodes[2] and set it as root's right child
- Create a new node with value nodes[3] and set it as root.left's left child
- Create a new node with value nodes[4] and set it as root.left's right child
- Create a new node with value nodes[5] and set it as root.right's left child
- Create a new node with value nodes[6] and set it as root.right's right child
Code
class Solution {
public:
void create_tree(node* root0, vector<int>& vec) {
// Level 1: create children of root
root0->left = new node(vec[1]);
root0->right = new node(vec[2]);
// Level 2: create children of root's left child
root0->left->left = new node(vec[3]);
root0->left->right = new node(vec[4]);
// Level 2: create children of root's right child
root0->right->left = new node(vec[5]);
root0->right->right = new node(vec[6]);
}
};class Solution:
def create_tree(self, root0, vec):
# Level 1: create children of root
root0.left = Node(vec[1])
root0.right = Node(vec[2])
# Level 2: create children of root's left child
root0.left.left = Node(vec[3])
root0.left.right = Node(vec[4])
# Level 2: create children of root's right child
root0.right.left = Node(vec[5])
root0.right.right = Node(vec[6])class Solution {
void createTree(Node root0, int[] vec) {
// Level 1: create children of root
root0.left = new Node(vec[1]);
root0.right = new Node(vec[2]);
// Level 2: create children of root's left child
root0.left.left = new Node(vec[3]);
root0.left.right = new Node(vec[4]);
// Level 2: create children of root's right child
root0.right.left = new Node(vec[5]);
root0.right.right = new Node(vec[6]);
}
}Complexity Analysis
Time Complexity: O(1)
We perform exactly 6 node creation and assignment operations. Since the array size is fixed at 7, the number of operations is constant and does not depend on any variable input size.
Space Complexity: O(1)
We only create 6 new nodes, which is a constant number. No additional data structures like queues or stacks are used. The space used does not grow with any variable input.
Why This Approach Is Not Efficient
While the direct assignment approach works perfectly for this specific problem (where the array always has exactly 7 elements), it has a fundamental limitation: it is not generalizable.
If the input array had 15 elements (4 levels) or 31 elements (5 levels) instead of 7, we would need to rewrite the entire function with more hardcoded lines. For an array of n elements, we would need n-1 individual assignment statements, each one manually specifying the exact path from the root (like root.left.right.left = ...). This makes the code:
- Brittle: Any change in the number of nodes requires rewriting the function
- Error-prone: As the tree grows deeper, the chain of
.leftand.rightbecomes long and easy to get wrong - Not reusable: The function only works for exactly 7 nodes — it cannot handle trees of different sizes
What we need is an algorithm that can construct a binary tree from a level-order array of any size, using a systematic process rather than manual wiring. The key insight is recognizing the pattern: in a level-order array, nodes are processed level by level, left to right — which is exactly what a queue-based breadth-first approach naturally does.
Optimal Approach - Level Order Queue Construction
Intuition
Instead of hardcoding each node's position, we can use a queue to systematically build the tree level by level — exactly mirroring how the array stores nodes in level order.
The core insight is this: in a level-order array, we process parent nodes from left to right. For each parent, the next two unprocessed elements in the array are its left and right children. A queue naturally maintains this "first come, first served" order — parents that were added earlier get their children assigned first.
Here's the pattern:
- Start with the root in the queue
- Take the front node from the queue (this is the next parent that needs children)
- The next array element becomes its left child — add this child to the queue
- The following array element becomes its right child — add this child to the queue
- Repeat until all array elements are used
This approach works for any array size, not just 7. Whether you have 3 nodes or 1000 nodes, the same algorithm correctly builds the complete binary tree.
Step-by-Step Explanation
Let's trace through with nodes = [1, 2, 3, 4, 5, 6, 7]:
Step 1: The root node (value 1) already exists. Place it into the queue. Set array index i = 1 (we start reading from the second element since root is already created).
- Queue: [Node(1)]
- i = 1
Step 2: Dequeue Node(1) — this is the current parent that needs children.
- Queue: []
- Current parent: Node(1)
Step 3: Read nodes[1] = 2. Create Node(2) and set it as the left child of Node(1). Enqueue Node(2). Increment i to 2.
- Queue: [Node(2)]
- i = 2
Step 4: Read nodes[2] = 3. Create Node(3) and set it as the right child of Node(1). Enqueue Node(3). Increment i to 3.
- Queue: [Node(2), Node(3)]
- i = 3
- Node(1) now has both children assigned.
Step 5: Dequeue Node(2) — this is the next parent.
- Queue: [Node(3)]
- Current parent: Node(2)
Step 6: Read nodes[3] = 4. Create Node(4) and set it as the left child of Node(2). Enqueue Node(4). Increment i to 4.
- Queue: [Node(3), Node(4)]
- i = 4
Step 7: Read nodes[4] = 5. Create Node(5) and set it as the right child of Node(2). Enqueue Node(5). Increment i to 5.
- Queue: [Node(3), Node(4), Node(5)]
- i = 5
Step 8: Dequeue Node(3) — this is the next parent.
- Queue: [Node(4), Node(5)]
- Current parent: Node(3)
Step 9: Read nodes[5] = 6. Create Node(6) and set it as the left child of Node(3). Enqueue Node(6). Increment i to 6.
- Queue: [Node(4), Node(5), Node(6)]
- i = 6
Step 10: Read nodes[6] = 7. Create Node(7) and set it as the right child of Node(3). Enqueue Node(7). Increment i to 7.
- Queue: [Node(4), Node(5), Node(6), Node(7)]
- i = 7
Step 11: i = 7 which equals the array length. All elements have been processed. The tree is fully constructed.
Level Order Queue Construction — BFS Tree Building — Watch how a queue processes parent nodes in level order, assigning the next two array elements as left and right children for each parent.
Algorithm
- Place the root node into a queue
- Initialize index i = 1 (pointing to the second element of the array)
- While i < array length:
a. Dequeue the front node — this is the current parent
b. If i < array length:- Create a new node with value nodes[i]
- Set it as the current parent's left child
- Enqueue this new node
- Increment i
c. If i < array length: - Create a new node with value nodes[i]
- Set it as the current parent's right child
- Enqueue this new node
- Increment i
- The tree is now fully constructed
Code
#include <queue>
using namespace std;
class Solution {
public:
void create_tree(node* root0, vector<int>& vec) {
queue<node*> q;
q.push(root0);
int i = 1;
while (i < vec.size()) {
node* curr = q.front();
q.pop();
// Assign left child from next array element
if (i < vec.size()) {
curr->left = new node(vec[i++]);
q.push(curr->left);
}
// Assign right child from next array element
if (i < vec.size()) {
curr->right = new node(vec[i++]);
q.push(curr->right);
}
}
}
};from collections import deque
class Solution:
def create_tree(self, root0, vec):
queue = deque([root0])
i = 1
while i < len(vec):
curr = queue.popleft()
# Assign left child from next array element
if i < len(vec):
curr.left = Node(vec[i])
queue.append(curr.left)
i += 1
# Assign right child from next array element
if i < len(vec):
curr.right = Node(vec[i])
queue.append(curr.right)
i += 1import java.util.LinkedList;
import java.util.Queue;
class Solution {
void createTree(Node root0, int[] vec) {
Queue<Node> queue = new LinkedList<>();
queue.add(root0);
int i = 1;
while (i < vec.length) {
Node curr = queue.poll();
// Assign left child from next array element
if (i < vec.length) {
curr.left = new Node(vec[i++]);
queue.add(curr.left);
}
// Assign right child from next array element
if (i < vec.length) {
curr.right = new Node(vec[i++]);
queue.add(curr.right);
}
}
}
}Complexity Analysis
Time Complexity: O(n)
We process each of the n elements in the array exactly once. For each element, we perform constant-time operations: creating a node, assigning it as a child, and enqueueing it. The queue operations (enqueue and dequeue) are each O(1). Therefore, the total time is O(n) where n is the number of elements in the array.
For this specific problem where n = 7, this is effectively O(1), but the algorithm scales linearly for any array size.
Space Complexity: O(n)
The queue holds at most one level of nodes at a time. For a complete binary tree with n nodes, the widest level has at most ⌈n/2⌉ nodes (the leaf level). Therefore, the queue can hold up to O(n) nodes in the worst case.
For this specific problem where n = 7, the maximum queue size is 4 (the leaf level), which is effectively O(1).