You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node { int val; Node *left; Node *right; Node *next; }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Example 1:
Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Example 2:
Input: root = [] Output: []
Constraints:
[0, 212 - 1]
.-1000 <= Node.val <= 1000
Follow-up:
Given a perfect binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
. Initially, all next pointers are set to NULL
.
Two approaches are presented here: Breadth-First Search (BFS) and Depth-First Search (DFS).
This approach uses a queue to perform a level-order traversal of the tree. For each level, it iterates through the nodes, linking each node's next
pointer to the next node in the level.
Algorithm:
NULL
, return NULL
. Otherwise, enqueue the root into a queue.size
times:
p
), link its next
pointer to the current node.p
to the current node.Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.
Space Complexity: O(W), where W is the maximum width of the tree (which is equal to 2h for a perfect binary tree of height h). In the worst-case scenario for a perfect binary tree, this is O(N).
This solution uses recursion to traverse the tree in a depth-first manner. It recursively connects the next
pointers within each level.
Algorithm:
dfs(left, right)
: This recursive function takes two nodes (left
and right
) as input, representing the left and right children of a parent node.left
or right
is NULL
, return.left.next
to right
.dfs
for the following pairs:
(left.left, left.right)
(left.right, right.left)
(right.left, right.right)
NULL
, call dfs(root.left, root.right)
.Time Complexity: O(N), where N is the number of nodes. Each node is visited and processed once.
Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In a perfect binary tree, H = log₂N, so the space complexity is O(log N).
The following code examples demonstrate both BFS and DFS solutions in several programming languages. Note that the Node
structure definition might need to be adapted depending on the specific environment.
(Note: Code examples for Python, Java, C++, Go, and TypeScript are provided in the original prompt response.)
Both BFS and DFS approaches solve the problem with a time complexity of O(N). However, BFS has a space complexity of O(N) in the worst case (for a perfect binary tree), while DFS has a space complexity of O(log N) for a perfect binary tree. Therefore, DFS is generally more space-efficient for this problem, especially for very wide trees. Choose the solution based on your specific needs and constraints.