Flatten binary tree nodes in level order from
The given problem involves flattening a binary tree into a singly linked list using a level-order traversal. Flattening a binary tree means rearranging the tree's nodes in such a way that all the nodes in the tree are connected through the right pointers, and the left pointers are set to null. The level-order traversal visits nodes level by level, and during this traversal, the tree is transformed into a flattened structure.
Problem Statement
The task is to create a Java program that flattens a binary tree into a singly linked list using a level-order traversal. After flattening, the program should print the data of each node in the linked list in a preorder sequence.
Explanation with Example
Let's consider the following binary tree:
1
/ \
2 3
/ / \
4 5 6
/ / \ \
7 8 9 11
Idea to Solve the Problem

To flatten the binary tree, we will use a level-order traversal technique with the help of a custom queue data structure. The process involves iterating through each level of the tree, adding the left and right child nodes to the queue, and unlinking the left subtree for each node, connecting the nodes through the right pointers.
Pseudocode
- Create the TreeNode class to represent binary tree nodes with data, left, and right pointers.
- Create the QNode class to represent nodes of a custom queue, which stores TreeNode elements.
- Implement the MyQueue class with methods to enqueue, dequeue, peek, check if the queue is empty, and get its size.
- Create the BinaryTree class with methods to perform a preorder traversal (preorder) and flatten the binary tree using level order (flattenLevelOrder).
- In the flattenLevelOrder() method:
- Initialize a temporary node (auxiliary) to the root of the binary tree.
- Create a new queue (MyQueue q).
- Enqueue the root node (auxiliary) into the queue.
- While the queue is not empty, do the following:
- Dequeue the current node from the queue.
- If the dequeued node has a left child, enqueue it into the queue.
- If the dequeued node has a right child, enqueue it into the queue.
- Unlink the left subtree by setting the left pointer of the dequeued node to null.
- Dequeue the node from the queue and store it in auxiliary.
- If the queue is not empty, set the right pointer of the auxiliary node to the front node of the queue.
- If the queue is empty, set the right pointer of the auxiliary node to null.
- Create a binary tree and add nodes to it.
- Call the flattenLevelOrder() method on the binary tree to flatten it.
- Call the showElement() method on the binary tree to print the data of the flattened tree in preorder.
Algorithm
The algorithm to flatten the binary tree using level order traversal is as follows:
- Start from the root node of the binary tree.
- Enqueue the root node into the queue.
- While the queue is not empty:
- Dequeue the current node from the front of the queue.
- If the dequeued node has a left child, enqueue it into the queue.
- If the dequeued node has a right child, enqueue it into the queue.
- Unlink the left subtree by setting the left pointer of the dequeued node to null.
- Dequeue the node from the queue and store it in the auxiliary variable.
- If the queue is not empty, set the right pointer of the auxiliary node to the front node of the queue.
- If the queue is empty, set the right pointer of the auxiliary node to null.
Code Solution
-
1) Flatten binary tree in order of level order traversal in java
2) Flatten binary tree in order of level order traversal c
3) Flatten binary tree in order of level order traversal golang
4) Flatten binary tree in order of level order traversal c++
5) Flatten binary tree in order of level order traversal c#
6) Flatten binary tree in order of level order traversal vb.net
7) Flatten binary tree in order of level order traversal typescript
8) Flatten binary tree in order of level order traversal node js
9) Flatten binary tree in order of level order traversal php
10) Flatten binary tree in order of level order traversal python
11) Flatten binary tree in order of level order traversal in ruby
12) Flatten binary tree in order of level order traversal in scala
13) Flatten binary tree in order of level order traversal in swift
14) Flatten binary tree in order of level order traversal in kotlin
Resultant Output Explanation
The program will print the data of each node in the flattened binary tree in preorder sequence. In the provided example, the binary tree looks like:
1
/ \
2 3
/ / \
4 5 6
/ / \ \
7 8 9 11
After flattening the tree, it will be represented as a singly linked list with right pointers:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 11
The preorder traversal of the binary tree will print the nodes in the order they appear in the flattened linked list:
Output: 1 2 3 4 5 6 7 8 9 11
Time Complexity
The time complexity of the flattenLevelOrder() method is O(N), where N is the number of nodes in the binary tree. This is because each node is visited once during the level-order traversal, and enqueueing and dequeueing operations on the queue take constant time. The showElement() method has a time complexity of O(N) as well, as it visits each node once to print its data. Overall, the time complexity of the entire program is O(N).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment