Invert alternate levels of a perfect binary tree
Write an efficient algorithm to invert alternate levels of a perfect binary tree.
For example, consider the following tree:
We should convert it into the following tree:
1. Using Level Order Traversal
The idea is to perform a level order traversal of the perfect binary tree and traverse its nodes level-by-level. Then for each odd level, push all nodes present in that level into a stack. Finally, at the end of each odd level, we put nodes present in the stack into their correct position. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <utility> #include <queue> #include <stack> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to print level order traversal of a perfect binary tree void levelOrderTraversal(Node* root) { if (root == nullptr) { return; } // create an empty queue and enqueue the root node queue<Node*> queue; queue.push(root); // pointer to store the current node Node* curr = nullptr; // loop till queue is empty while (queue.size()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.front(); queue.pop(); cout << curr->data << " "; if (curr->left) { queue.push(curr->left); } if (curr->right) { queue.push(curr->right); } } } // Iterative function to invert alternate levels of a perfect binary tree // using level order traversal void invertBinaryTree(Node* root) { // base case: if the tree is empty if (root == nullptr) { return; } // maintain a queue and enqueue the root node queue<Node*> q; q.push(root); // to store current level information bool level = false; // maintain another queue to store nodes present at an odd level queue<Node*> level_nodes; // maintain a stack to store node's data on an odd level stack<int> level_data; // loop till queue is empty while (!q.empty()) { // get the size of the current level int n = q.size(); // process all nodes present at the current level while (n--) { // dequeue front node Node* curr = q.front(); q.pop(); // if the level is odd if (level) { // enqueue current node level_nodes.push(curr); // push the current node data into the stack level_data.push(curr->data); } // if the current node is the last node of the level if (n == 0) { // flip the level level = !level; // put elements present in the `level_data` into their correct // position using `level_nodes` while (!level_nodes.empty()) { Node* front = level_nodes.front(); front->data = level_data.top(); level_nodes.pop(); level_data.pop(); } } // enqueue left child of the current node if (curr->left) { q.push(curr->left); } // enqueue right child of the current node if (curr->right) { q.push(curr->right); } } } } int main() { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->left = new Node(12); root->right->left->right = new Node(13); root->right->right->left = new Node(14); root->right->right->right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); return 0; } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; // A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class Main { // Function to print level order traversal of a perfect binary tree public static void levelOrderTraversal(Node root) { if (root == null) { return; } // create an empty queue and enqueue the root node Queue<Node> queue = new ArrayDeque<>(); queue.add(root); // to store the current node Node curr = null; // loop till queue is empty while (!queue.isEmpty()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.poll(); System.out.print(curr.data + " "); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } } // Iterative function to invert alternate levels of a perfect binary tree // using level order traversal public static void invertBinaryTree(Node root) { // base case: if the tree is empty if (root == null) { return; } // maintain a queue and enqueue the root node Queue<Node> q = new ArrayDeque<>(); q.add(root); // to store current level information boolean level = false; // maintain another queue to store nodes present at an odd level Queue<Node> level_nodes = new ArrayDeque<>(); // maintain a stack to store node's data on an odd level Stack<Integer> level_data = new Stack<>(); // loop till queue is empty while (!q.isEmpty()) { // get the size of the current level int n = q.size(); // process all nodes present at the current level while (n-- > 0) { // dequeue front node Node curr = q.poll(); // if the level is odd if (level) { // enqueue current node level_nodes.add(curr); // push the current node data into the stack level_data.add(curr.data); } // if the current node is the last node of the level if (n == 0) { // flip the level level = !level; // put elements present in the `level_data` into their correct // position using `level_nodes` while (!level_nodes.isEmpty()) { Node front = level_nodes.poll(); front.data = level_data.pop(); } } // enqueue left child of the current node if (curr.left != null) { q.add(curr.left); } // enqueue right child of the current node if (curr.right != null) { q.add(curr.right); } } } } public static void main(String[] args) { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.left = new Node(12); root.right.left.right = new Node(13); root.right.right.left = new Node(14); root.right.right.right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); } } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
from collections import deque # A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to print level order traversal of a perfect binary tree def levelOrderTraversal(root): if root is None: return # create an empty queue and enqueue the root node queue = deque() queue.append(root) # loop till queue is empty while queue: # process each node in the queue and enqueue their # non-empty left and right child curr = queue.popleft() print(curr.data, end=' ') if curr.left: queue.append(curr.left) if curr.right: queue.append(curr.right) # Iterative function to invert alternate levels of a perfect binary tree # using level order traversal def invertBinaryTree(root): # base case: if the tree is empty if root is None: return # maintain a queue and enqueue the root node q = deque() q.append(root) # to store current level information level = False # maintain another queue to store nodes present at an odd level level_nodes = deque() # maintain a stack to store node's data on an odd level level_data = deque() # loop till queue is empty while q: # get the size of the current level size = len(q) # process all nodes present at the current level for n in reversed(range(size)): # dequeue front node curr = q.popleft() # if the level is odd if level: # enqueue current node level_nodes.append(curr) # push the current node data into the stack level_data.append(curr.data) # if the current node is the last node of the level if n == 0: # flip the level level = not level # put elements present in the `level_data` into their correct # position using `level_nodes` while level_nodes: front = level_nodes.popleft() # use `popleft()` for queue front.data = level_data.pop() # use `pop()` for stack # enqueue left child of the current node if curr.left: q.append(curr.left) # enqueue right child of the current node if curr.right: q.append(curr.right) if __name__ == '__main__': ''' Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(10) root.left.right.right = Node(11) root.right.left.left = Node(12) root.right.left.right = Node(13) root.right.right.left = Node(14) root.right.right.right = Node(15) invertBinaryTree(root) levelOrderTraversal(root) |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(n) extra space for storing nodes present at odd levels of a binary tree. The stack is preferred over a list for storing nodes since it is a LIFO data structure, and we don’t need to reverse it before assigning value to nodes.
2. Using Inorder Traversal
The idea remains similar to the previous approach, except here we recursively traverse the tree in an inorder fashion, and store nodes present all odd levels in a stack, and replace them later by doing another inorder traversal. This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
#include <iostream> #include <vector> #include <queue> #include <stack> #include <string> #include <utility> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to print level order traversal of a given binary tree void levelOrderTraversal(Node* root) { if (root == nullptr) { return; } // create an empty queue and enqueue the root node queue<Node*> queue; queue.push(root); // pointer to store the current node Node* curr = nullptr; // loop till queue is empty while (queue.size()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.front(); queue.pop(); cout << curr->data << " "; if (curr->left) { queue.push(curr->left); } if (curr->right) { queue.push(curr->right); } } } // Recursive function to store nodes of odd levels in a stack using inorder traversal void pushOddLevelNodes(Node* root, stack<int> &s, bool level) { // base case if (root == nullptr) { return; } // store nodes in the left subtree pushOddLevelNodes(root->left, s, !level); // push the current node's data into the stack only if the level is odd if (level) { s.push(root->data); } // store nodes in the right subtree pushOddLevelNodes(root->right, s, !level); } // Recursive function to invert alternate levels of a perfect binary tree // using inorder traversal void invertBinaryTree(Node* root, stack<int> &s, bool level) { // base case if (root == nullptr) { return; } // invert nodes in the left subtree invertBinaryTree(root->left, s, !level); // if the level is odd if (level) { // pop an element from the stack and assign it to the current node root->data = s.top(); s.pop(); } // invert nodes in the right subtree invertBinaryTree(root->right, s, !level); } // Invert alternate levels of a perfect binary tree void invertBinaryTree(Node* root) { // create a stack and push nodes of odd levels into it stack<int> s; pushOddLevelNodes(root, s, false); // put nodes of odd levels at their correct position using stack invertBinaryTree(root, s, false); } int main() { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->left = new Node(12); root->right->left->right = new Node(13); root->right->right->left = new Node(14); root->right->right->right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); return 0; } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; // A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class Main { // Function to print level order traversal of a given binary tree public static void levelOrderTraversal(Node root) { if (root == null) { return; } // create an empty queue and enqueue the root node Queue<Node> queue = new ArrayDeque<>(); queue.add(root); // to store the current node Node curr = null; // loop till queue is empty while (!queue.isEmpty()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.poll(); System.out.print(curr.data + " "); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } } // Recursive function to store nodes of odd levels in a stack using // inorder traversal public static void pushOddLevelNodes(Node root, Stack<Integer> s, boolean level) { // base case if (root == null) { return; } // store nodes in the left subtree pushOddLevelNodes(root.left, s, !level); // push the current node's data into the stack only if the level is odd if (level) { s.add(root.data); } // store nodes in the right subtree pushOddLevelNodes(root.right, s, !level); } // Recursive function to invert alternate levels of a perfect binary tree // using inorder traversal public static void invertBinaryTree(Node root, Stack<Integer> s, boolean level) { // base case if (root == null) { return; } // invert nodes in the left subtree invertBinaryTree(root.left, s, !level); // if the level is odd if (level) { // pop an element from the stack and assign it to the current node root.data = s.pop(); } // invert nodes in the right subtree invertBinaryTree(root.right, s, !level); } // Invert alternate levels of a perfect binary tree public static void invertBinaryTree(Node root) { // create a stack and push nodes of odd levels into it Stack<Integer> s = new Stack<>(); pushOddLevelNodes(root, s, false); // put nodes of odd levels at their correct position using stack invertBinaryTree(root, s, false); } public static void main(String[] args) { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.left = new Node(12); root.right.left.right = new Node(13); root.right.right.left = new Node(14); root.right.right.right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); } } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
from collections import deque # A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to print level order traversal of a given binary tree def levelOrderTraversal(root): if root is None: return # create an empty queue and enqueue the root node queue = deque() queue.append(root) # loop till queue is empty while queue: # process each node in the queue and enqueue their # non-empty left and right child curr = queue.popleft() print(curr.data, end=' ') if curr.left: queue.append(curr.left) if curr.right: queue.append(curr.right) # Recursive function to store nodes of odd levels in a stack using inorder traversal def pushOddLevelNodes(root, s, level): # base case if root is None: return # store nodes in the left subtree pushOddLevelNodes(root.left, s, not level) # push the current node's data into the stack only if the level is odd if level: s.append(root.data) # store nodes in the right subtree pushOddLevelNodes(root.right, s, not level) # Recursive function to invert alternate levels of a perfect binary tree # using inorder traversal def invertBinaryTree(root, s, level): # base case if root is None: return # invert nodes in the left subtree invertBinaryTree(root.left, s, not level) # if the level is odd if level: # pop an element from the stack and assign it to the current node root.data = s.pop() # invert nodes in the right subtree invertBinaryTree(root.right, s, not level) # Invert alternate levels of a perfect binary tree def invertBT(root): # create a stack and push nodes of odd levels into it s = deque() pushOddLevelNodes(root, s, False) # put nodes of odd levels at their correct position using stack invertBinaryTree(root, s, False) if __name__ == '__main__': ''' Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(10) root.left.right.right = Node(11) root.right.left.left = Node(12) root.right.left.right = Node(13) root.right.right.left = Node(14) root.right.right.right = Node(15) invertBT(root) levelOrderTraversal(root) |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(n) extra space for storing nodes of odd levels.
We can replace stack with queue by doing reverse inorder traversal in the pushOddLevelNodes() function, i.e., call the right child before the left child. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <utility> #include <queue> #include <stack> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to print level order traversal of a given binary tree void levelOrderTraversal(Node* root) { if (root == nullptr) { return; } // create an empty queue and enqueue the root node queue<Node*> queue; queue.push(root); // pointer to store the current node Node* curr = nullptr; // loop till queue is empty while (queue.size()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.front(); queue.pop(); cout << curr->data << " "; if (curr->left) { queue.push(curr->left); } if (curr->right) { queue.push(curr->right); } } } // Recursive function to store nodes of odd levels in a queue // using inorder traversal void pushOddLevelNodes(Node* root, queue<int> &q, bool level) { // base case if (root == nullptr) { return; } // store nodes in the right subtree pushOddLevelNodes(root->right, q, !level); // enqueue current node's data only if the level is odd if (level) { q.push(root->data); } // store nodes in the left subtree pushOddLevelNodes(root->left, q, !level); } // Recursive function to invert alternate levels of a perfect binary tree // using inorder traversal void invertBinaryTree(Node* root, queue<int> &q, bool level) { // base case if (root == nullptr) { return; } // invert nodes in the left subtree invertBinaryTree(root->left, q, !level); // if the level is odd if (level) { // dequeue front element and assign it to the current node root->data = q.front(); q.pop(); } // invert nodes in the right subtree invertBinaryTree(root->right, q, !level); } // Invert alternate levels of a perfect binary tree void invertBinaryTree(Node* root) { // create a queue and push nodes of odd levels into it queue<int> q; pushOddLevelNodes(root, q, false); // put nodes of odd levels at their correct position using a queue invertBinaryTree(root, q, false); } int main() { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->left = new Node(12); root->right->left->right = new Node(13); root->right->right->left = new Node(14); root->right->right->right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); return 0; } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
import java.util.ArrayDeque; import java.util.Queue; // A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class Main { // Function to print level order traversal of a given binary tree public static void levelOrderTraversal(Node root) { if (root == null) { return; } // create an empty queue and enqueue the root node Queue<Node> queue = new ArrayDeque<>(); queue.add(root); // to store the current node Node curr = null; // loop till queue is empty while (!queue.isEmpty()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.poll(); System.out.print(curr.data + " "); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } } // Recursive function to store nodes of odd levels in a queue // using inorder traversal public static void pushOddLevelNodes(Node root, Queue<Integer> q, boolean level) { // base case if (root == null) { return; } // store nodes in the right subtree pushOddLevelNodes(root.right, q, !level); // enqueue current node's data only if the level is odd if (level) { q.add(root.data); } // store nodes in the left subtree pushOddLevelNodes(root.left, q, !level); } // Recursive function to invert alternate levels of a perfect binary tree // using inorder traversal public static void invertBinaryTree(Node root, Queue<Integer> q, boolean level) { // base case if (root == null) { return; } // invert nodes in the left subtree invertBinaryTree(root.left, q, !level); // if the level is odd if (level) { // dequeue front element and assign it to the current node root.data = q.poll(); } // invert nodes in the right subtree invertBinaryTree(root.right, q, !level); } // Invert alternate levels of a perfect binary tree public static void invertBinaryTree(Node root) { // create a queue and push nodes of odd levels into it Queue<Integer> q = new ArrayDeque<>(); pushOddLevelNodes(root, q, false); // put nodes of odd levels at their correct position using a queue invertBinaryTree(root, q, false); } public static void main(String[] args) { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.left = new Node(12); root.right.left.right = new Node(13); root.right.right.left = new Node(14); root.right.right.right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); } } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
from collections import deque # A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to print level order traversal of a given binary tree def levelOrderTraversal(root): if root is None: return # create an empty queue and enqueue the root node queue = deque() queue.append(root) # loop till queue is empty while queue: # process each node in the queue and enqueue their # non-empty left and right child curr = queue.popleft() print(curr.data, end=' ') if curr.left: queue.append(curr.left) if curr.right: queue.append(curr.right) # Recursive function to store nodes of odd levels in a queue # using inorder traversal def pushOddLevelNodes(root, q, level): # base case if root is None: return # store nodes in the right subtree pushOddLevelNodes(root.right, q, not level) # enqueue current node's data only if the level is odd if level: q.append(root.data) # store nodes in the left subtree pushOddLevelNodes(root.left, q, not level) # Recursive function to invert alternate levels of a perfect binary tree # using inorder traversal def invertBinaryTree(root, q, level): # base case if root is None: return # invert nodes in the left subtree invertBinaryTree(root.left, q, not level) # if the level is odd if level: # dequeue front element and assign it to the current node root.data = q.popleft() # invert nodes in the right subtree invertBinaryTree(root.right, q, not level) # Invert alternate levels of a perfect binary tree def invertBT(root): # create a queue and push nodes of odd levels into it q = deque() pushOddLevelNodes(root, q, False) # put nodes of odd levels at their correct position using a queue invertBinaryTree(root, q, False) if __name__ == '__main__': root = None ''' Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(10) root.left.right.right = Node(11) root.right.left.left = Node(12) root.right.left.right = Node(13) root.right.right.left = Node(14) root.right.right.right = Node(15) invertBT(root) levelOrderTraversal(root) |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
3. Using Preorder Traversal
The above solution requires two traversals of the binary tree and also needs a stack data structure. We can invert alternate levels of a perfect binary tree in single tree traversal and without any explicit stack. The idea is to perform a modified preorder traversal of the tree and use level information to swap the data within the function itself. It is a little tricky and requires special attention.
The implementation can be seen below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <utility> #include <list> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to print level order traversal of a perfect binary tree void levelOrderTraversal(Node* root) { if (root == nullptr) { return; } // create an empty queue and enqueue the root node list<Node*> queue; queue.push_back(root); // pointer to store the current node Node* curr = nullptr; // loop till queue is empty while (queue.size()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.front(); queue.pop_front(); cout << curr->data << " "; if (curr->left) { queue.push_back(curr->left); } if (curr->right) { queue.push_back(curr->right); } } } // Recursive function to invert alternate levels of a perfect binary tree // using preorder traversal void invertBinaryTree(Node* first, Node* second, bool level) { // return if either child is empty if (!first || !second) { return; } // swap data only if the level is odd if (level) { swap(first->data, second->data); } // recur with the left child of `first` and the right child // of `second` with an updated level invertBinaryTree(first->left, second->right, !level); // recur with the right child of `first` and left child of // `second` with an updated level invertBinaryTree(first->right, second->left, !level); } void invertBinaryTree(Node* root) { // base case if (root == nullptr) { return; } invertBinaryTree(root->left, root->right, true); } int main() { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->left = new Node(12); root->right->left->right = new Node(13); root->right->right->left = new Node(14); root->right->right->right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); return 0; } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
import java.util.ArrayDeque; import java.util.Queue; // A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class Main { // Function to print level order traversal of a perfect binary tree public static void levelOrderTraversal(Node root) { if (root == null) { return; } // create an empty queue and enqueue the root node Queue<Node> queue = new ArrayDeque<>(); queue.add(root); // to store the current node Node curr = null; // loop till queue is empty while (!queue.isEmpty()) { // process each node in the queue and enqueue their // non-empty left and right child curr = queue.poll(); System.out.print(curr.data + " "); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } } // Recursive function to invert alternate levels of a perfect binary tree // using preorder traversal public static void invertBinaryTree(Node first, Node second, boolean level) { // return if either child is empty if (first == null || second == null) { return; } // swap data only if the level is odd if (level) { int temp = first.data; first.data = second.data; second.data = temp; } // recur with the left child of `first` and the right child // of `second` with an updated level invertBinaryTree(first.left, second.right, !level); // recur with the right child of `first` and left child of // `second` with an updated level invertBinaryTree(first.right, second.left, !level); } public static void invertBinaryTree(Node root) { // base case if (root == null) { return; } invertBinaryTree(root.left, root.right, true); } public static void main(String[] args) { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.left = new Node(12); root.right.left.right = new Node(13); root.right.right.left = new Node(14); root.right.right.right = new Node(15); invertBinaryTree(root); levelOrderTraversal(root); } } |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
from collections import deque # A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to print level order traversal of a perfect binary tree def levelOrderTraversal(root): if root is None: return # create an empty queue and enqueue the root node queue = deque() queue.append(root) # loop till queue is empty while queue: # process each node in the queue and enqueue their # non-empty left and right child curr = queue.popleft() print(curr.data, end=' ') if curr.left: queue.append(curr.left) if curr.right: queue.append(curr.right) # Recursive function to invert alternate levels of a perfect binary tree # using preorder traversal def invertBinaryTree(first, second, level): # return if either child is empty if first is None or second is None: return # swap data only if the level is odd if level: temp = first.data first.data = second.data second.data = temp # recur with the left child of `first` and the right child of # `second` with an updated level invertBinaryTree(first.left, second.right, not level) # recur with the right child of `first` and left child of # `second` with an updated level invertBinaryTree(first.right, second.left, not level) def invertBT(root): # base case if not root: return invertBinaryTree(root.left, root.right, True) if __name__ == '__main__': root = None ''' Construct the following tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(10) root.left.right.right = Node(11) root.right.left.left = Node(12) root.right.left.right = Node(13) root.right.right.left = Node(14) root.right.right.right = Node(15) invertBT(root) levelOrderTraversal(root) |
Output:
1 3 2 4 5 6 7 15 14 13 12 11 10 9 8
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)