Given an integer N, the task is to generate a perfect binary tree with height N such that each node has a value that is the same as its depth. Return the inorder traversal of the generated binary tree.
A Perfect binary tree is a type of binary tree where every internal node has exactly two child nodes and all leaf nodes are at same level.
Examples:
Input: N = 2
Output: 2 1 2 0 2 1 2
Explanation: The structure of the tree is as following
Perfect Binary Tree with height 2
Input: N = 1
Output: 1 0 1
Approach: The problem can be solved using level order traversal based on the following observation:
As there is a requirement to fill each node with the value that is the same as its depth so use the level order traversal. In each step fill a total level and mark all the nodes with the value same as the depth.
Follow the steps mentioned below to implement the approach:
- Initiate a variable to store the depth of the current level.
- Initiate a queue to store the node of each level and perform the level order traversal.
- In each iteration get all the nodes in that level and continue the following until the depth is N:
- Increase the depth by 1.
- Pop the nodes at the current level.
- Generate the child nodes for each node.
- Add the new child nodes for further processing.
- After the traversal is complete, the tree is prepared.
- Print the inorder traversal of the tree.
Below is the implementation of the above approach.
C++
//C++ code to implement the approach#include <iostream>#include <queue>using namespace std;// Class to hold tree node data// and left, right childrenclass TreeNode {public: long val; TreeNode* left; TreeNode* right; TreeNode(long x) { val = x; left = NULL; right = NULL; }};// Class to create the perfect binary treeclass BinaryTree { // Method to construct a binary treepublic: static TreeNode* perfectBinaryTree(int depth) { // Return root with 0 as val if height is 0 if (depth == 0) return new TreeNode(0); // Initiate queue to store // the nodes on each level queue<TreeNode*> queue; // Create a root node with value 0 long i = 0; TreeNode* root = new TreeNode(i); // Add the root node to the queue // for further processing queue.push(root); // Iterate through the queue till its empty while (!queue.empty()) { // Check the size of the queue to iterate // through each node on the same level int size = queue.size(); // Increment the value of node // upon each level i++; // Break the loop if the value of the node // reaches given depth // else process the node in the queue if (i > depth) { break; } else { // Add the left and right child // for the node in the queue and // add those newly created child nodes // to the queue. for (int j = 0; j < size; j++) { TreeNode* node = queue.front(); queue.pop(); node->left = new TreeNode(i); node->right = new TreeNode(i); queue.push(node->left); queue.push(node->right); } } } // Return the root of the tree return root; } // Inorder traversal of the tree (Left Root Right)public: static void inOrderTraversal(TreeNode* node) { if (node == NULL) return; inOrderTraversal(node->left); cout << node->val << " "; inOrderTraversal(node->right); }};// Driver codeint main() { int N = 2; // Function call to build the tree TreeNode* binaryTreeRoot = BinaryTree::perfectBinaryTree(N); // Function call to print the tree BinaryTree::inOrderTraversal(binaryTreeRoot); return 0;} |
Java
// Java code to implement the approachimport java.util.*;// Class to hold tree node data// and left, right childrenclass TreeNode { public long val; public TreeNode left; public TreeNode right; public TreeNode(long x) { val = x; left = null; right = null; }}// Class to create the perfect binary treeclass BinaryTree { // Method to construct a binary tree public static TreeNode perfectBinaryTree(int depth) { // Return root with 0 as val if height is 0 if (depth == 0) return new TreeNode(0); // Initiate queue to store // the nodes on each level Queue<TreeNode> queue = new LinkedList<>(); // Create a root node with value 0 long i = 0; TreeNode root = new TreeNode(i); // Add the root node to the queue // for further processing queue.add(root); // Iterate through the queue till its empty while (!queue.isEmpty()) { // Check the size of the queue to iterate // through each node on the same level int size = queue.size(); // Increment the value of node // upon each level i++; // Break the loop if the value of the node // reaches given depth // else process the node in the queue if (i > depth) { break; } else { // Add the left and right child // for the node in the queue and // add those newly created child nodes // to the queue. for (int j = 0; j < size; j++) { TreeNode node = queue.remove(); node.left = new TreeNode(i); node.right = new TreeNode(i); queue.add(node.left); queue.add(node.right); } } } // Return the root of the tree return root; } // Inorder traversal of the tree (Left Root Right) public static void inOrderTraversal(TreeNode node) { if (node == null) return; inOrderTraversal(node.left); System.out.print(node.val + " "); inOrderTraversal(node.right); } // Driver code public static void main(String[] args) { int N = 2; // Function call to build the tree TreeNode binaryTreeRoot = perfectBinaryTree(N); // Function call to print the tree inOrderTraversal(binaryTreeRoot); }} |
Python3
# Python code to implement the approach # Class to hold tree node data# and left, right childrenclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None# Class to create the perfect binary treeclass BinaryTree: # Method to construct a binary tree def perfectBinaryTree(self, depth): # Return root with 0 as val if height is 0 if depth == 0: return TreeNode(0) # Initiate queue to store # the nodes on each level queue = [] # Create a root node with value 0 i = 0 root = TreeNode(i) # Add the root node to the queue # for further processing queue.append(root) # Iterate through the queue till its empty while len(queue) > 0: # Check the size of the queue to iterate # through each node on the same level size = len(queue) # Increment the value of node # upon each level i += 1 # Break the loop if the value of the node # reaches given depth # else process the node in the queue if i > depth: break else: # Add the left and right child # for the node in the queue and # add those newly created child nodes # to the queue. for j in range(size): node = queue.pop(0) node.left = TreeNode(i) node.right = TreeNode(i) queue.append(node.left) queue.append(node.right) # Return the root of the tree return root # Inorder traversal of the tree (Left Root Right) def inOrderTraversal(self, node): if node is None: return self.inOrderTraversal(node.left) print(node.val, end=" ") self.inOrderTraversal(node.right) # Driver code def main(self): N = 2 # Function call to build the tree binaryTreeRoot = self.perfectBinaryTree(N) # Function call to print the tree self.inOrderTraversal(binaryTreeRoot)# Create an object of the BinaryTree classbTree = BinaryTree()# Call the main functionbTree.main() |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;// Class to hold tree node data// and left, right childrenpublic class TreeNode { public long val; public TreeNode left; public TreeNode right; public TreeNode(long x) { val = x; left = null; right = null; }}// Class to create the perfect binary treepublic class BinaryTree { // Method to construct a binary tree public static TreeNode perfectBinaryTree(int depth) { // Return root with 0 as val if height is 0 if (depth == 0) return new TreeNode(0); // Initiate queue to store // the nodes on each level Queue<TreeNode> queue = new Queue<TreeNode>(); // Create a root node with value 0 long i = 0; TreeNode root = new TreeNode(i); // Add the root node to the queue // for further processing queue.Enqueue(root); // Iterate through the queue till its empty while (queue.Count!=0) { // Check the size of the queue to iterate // through each node on the same level int size = queue.Count; // Increment the value of node // upon each level i++; // Break the loop if the value of the node // reaches given depth // else process the node in the queue if (i > depth) { break; } else { // Add the left and right child // for the node in the queue and // add those newly created child nodes // to the queue. for (int j = 0; j < size; j++) { TreeNode node = queue.Dequeue(); node.left = new TreeNode(i); node.right = new TreeNode(i); queue.Enqueue(node.left); queue.Enqueue(node.right); } } } // Return the root of the tree return root; } // Inorder traversal of the tree (Left Root Right) public static void inOrderTraversal(TreeNode node) { if (node == null) return; inOrderTraversal(node.left); Console.Write(node.val + " "); inOrderTraversal(node.right); } // Driver code public static void Main(String[] args) { int N = 2; // Function call to build the tree TreeNode binaryTreeRoot = perfectBinaryTree(N); // Function call to print the tree inOrderTraversal(binaryTreeRoot); }}// This code is contributed by shikhasingrajput |
Javascript
// JavaScript code for the above approach class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}class BinaryTree { static perfectBinaryTree(depth) { if (depth === 0) { return new TreeNode(0); } const queue = []; let i = 0; const root = new TreeNode(i); queue.push(root); while (queue.length > 0) { const size = queue.length; i++; if (i > depth) { break; } else { for (let j = 0; j < size; j++) { const node = queue.shift(); node.left = new TreeNode(i); node.right = new TreeNode(i); queue.push(node.left); queue.push(node.right); } } } return root; } static inOrderTraversal(node) { if (node === null) return; this.inOrderTraversal(node.left); console.log(node.val + " "); this.inOrderTraversal(node.right); }}const N = 2;const binaryTreeRoot = BinaryTree.perfectBinaryTree(N);BinaryTree.inOrderTraversal(binaryTreeRoot); // This code is contributed by Potta Lokesh. |
Output
2 1 2 0 2 1 2
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
