Construct a Perfect Binary Tree with given Height

0 0 7 minutes read

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 children
class TreeNode {
public:
    long val;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(long x) {
        val = x;
        left = NULL;
        right = NULL;
    }
};
 
// Class to create the perfect binary tree
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;
 
        // 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 code
int 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 approach
 
import java.util.*;
 
// Class to hold tree node data
// and left, right children
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 tree
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 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 children
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
# Class to create the perfect binary tree
class 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 class
bTree = BinaryTree()
 
# Call the main function
bTree.main()

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
// Class to hold tree node data
// and left, right children
public 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 tree
public 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(2^N)
Auxiliary Space: O(2^N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!