Print all nodes less than a given value in a Max Heap

In this post, we explore the problem of printing all nodes in a Max Heap that are less than a given value. A Max Heap is a binary tree structure where the value of each node is greater than or equal to the values of its children. We will discuss the approach to solving this problem, provide the necessary code, and analyze its time complexity.

Problem Statement and Description

Given a Max Heap and a target value k, the task is to print all nodes in the Max Heap that have values less than k. In other words, we need to identify and print the nodes that are smaller than the given value k, while maintaining the Max Heap property.

Example

Consider the Max Heap shown below:

            14
          /    \
         11      9
       /   \    /  \
      6     7  4    2
     / \   /
    1   3 5

If the target value k is 10, the nodes with values less than 10 are 1, 6, 3, 5, 7, 4, 9, and 2. The expected output is 1 6 3 5 7 4 9 2.

Approach

The main idea behind solving this problem is to traverse the Max Heap in an in-order manner while checking the values of nodes. Since in a Max Heap, parent nodes are always greater than their children, we can efficiently decide whether to traverse a subtree or not based on the value of the current node.

Pseudocode

function printNodesLessThanK(node, k)
    if node is null
        return
    printNodesLessThanK(node.left, k)
    if node.value < k
        print node.value
    printNodesLessThanK(node.right, k)
end function

main()
    heap = createMaxHeap()
    // Construct the Max Heap (insertions)

    k = 10
    printNodesLessThanK(heap.root, k)
end main

Algorithm Explanation

1. Create a class Node representing a node in the Max Heap with left, right, and key attributes.
2. Create a class MaxHeap with attributes size and root. The root attribute points to the root of the Max Heap, and size keeps track of the number of nodes.
3. Implement the printNodesLessThanK function recursively:
   • Base case: If the current node is null, return.
   • Recursively call printNodesLessThanK on the left subtree.
   • If the value of the current node is less than k, print the value.
   • Recursively call printNodesLessThanK on the right subtree.
4. In the main function, create an instance of MaxHeap, perform insertions to construct the Max Heap, and define the value of k.
5. Call the printNodesLessThanK function with the root node of the Max Heap and value k.

Code Solution

• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

/*
  C++ program
  Print all nodes less than a given value in a Max Heap
*/
//Tree node
#include<iostream>

using namespace std;
class Node {
	public:

	//Left and right child
	Node *left;
	Node *right;
	//Data value
	int key;
	Node(int key) {
		this->key = key;
		this->left = NULL;
		this->right = NULL;
	}
};
class MaxHeap {
	public:

	//This is use to store information of number of nodes in Max heap
	int size;
	Node *root;
	MaxHeap() {
		this->root = NULL;
		this->size = 0;
	}
	//Get height of insert new node
	int insertHeight() {
		int i = 1;
		int sum = 0;
		while (this->size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	void swapNode(Node *first, Node *second) {
		int key = first->key;
		first->key = second->key;
		second->key = key;
	}
	//Arrange node key
	void arrangeNode(Node *root) {
		if (root->left != NULL && root->left->key > root->key) {
			this->swapNode(root, root->left);
		}
		if (root->right != NULL && root->right->key > root->key) {
			this->swapNode(root, root->right);
		}
	}
	bool addNode(Node *root, int height, int level, int key) {
		if (level >= height) {
			return false;
		}
		if (root != NULL) {
			if (level - 1 == height && root->left == NULL || root->right == NULL) {
				if (root->left == NULL) {
					root->left = new Node(key);
				} else {
					root->right = new Node(key);
				}
				this->arrangeNode(root);
				return true;
			}
			if (this->addNode(root->left, height, level + 1, key) || 
                this->addNode(root->right, height, level + 1, key)) {
				//Check effect of new inserted node
				this->arrangeNode(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	void insert(int key) {
		//Test case

		if (this->root == NULL) {
			this->root = new Node(key);
		} else
		if (this->root->left == NULL) {
			this->root->left = new Node(key);
			this->arrangeNode(this->root);
		} else
		if (this->root->right == NULL) {
			this->root->right = new Node(key);
			this->arrangeNode(this->root);
		} else {
			int height = this->insertHeight();
			this->addNode(this->root, height, 0, key);
		}
		this->size++;
	}
	void printNode(Node *root, int key) {
		if (root != NULL) {
			this->printNode(root->left, key);
			if (root->key < key) {
				//When element is less than of given key value

				cout << " " << root->key;
			}
			this->printNode(root->right, key);
		}
	}
};
int main() {
	MaxHeap heap =  MaxHeap();
	//Construct Min heap tree
	heap.insert(5);
	heap.insert(7);
	heap.insert(4);
	heap.insert(3);
	heap.insert(9);
	heap.insert(14);
	heap.insert(2);
	heap.insert(1);
	heap.insert(6);
	heap.insert(11);
	/*After insert element*/
	/*
	               14
	             /    \
	            11      9
	          /   \    /  \
	         6     7  4    2
	        / \   /
	       1   3 5
	    */
	int k = 10;
	heap.printNode(heap.root, k);
	return 0;
}

 1 6 3 5 7 4 9 2

/*
  Java program
  Print all nodes less than a given value in a Max Heap
*/
//Tree node
class Node {
  //Left and right child
  public Node left;
  public Node right;

  //Data value
  public int key;

  public Node(int key) {
    this.key = key;

    left = null;
    right = null;
  }
}
public class MaxHeap {


  //This is use to store information of number of nodes in Max heap
  public int size;

  public Node root;

  public MaxHeap() {
    root = null;

    size = 0;
  }

  //Get height of insert new node
  public int insertHeight() {
    int i = 1;

    int sum = 0;

    while (this.size > sum + (1 << i)) {
      sum += (1 << i);
      i++;
    }
    return i;
  }
  public void swapNode(Node first, Node second) {
    int key = first.key;

    first.key = second.key;
    second.key = key;
  }
  //Arrange node key
  public void arrangeNode(Node root) {

    if (root.left != null && root.left.key > root.key) {
      swapNode(root, root.left);
    }
    if (root.right != null && root.right.key > root.key) {
      swapNode(root, root.right);
    }
  }
  public boolean addNode(Node root, int height, int level, int key) {
    if (level >= height) {
      return false;
    }
    if (root != null) {

      if (level - 1 == height && root.left == null || root.right == null) {
        if (root.left == null) {
          root.left = new Node(key);
        } else {
          root.right = new Node(key);
        }

        arrangeNode(root);

        return true;
      }

      if (addNode(root.left, height, level + 1, key) || addNode(root.right, height, level + 1, key)) {
        //Check effect of new inserted node
        arrangeNode(root);

        return true;
      }


    }
    return false;
  }
  //Handles the request to new inserting node
  public void insert(int key) {
    //Test case
    if (root == null) {
      root = new Node(key);
    } else if (root.left == null) {
      root.left = new Node(key);
      arrangeNode(root);

    } else if (root.right == null) {
      root.right = new Node(key);
      arrangeNode(root);
    } else {
      int height = insertHeight();

      addNode(root, height, 0, key);
    }
    this.size++;
  }

  public void printNode(Node root, int key) 
  {
    if (root != null) {


      printNode(root.left, key);

      if (root.key < key) {
        //When element is less than of given key value
        System.out.print("  " + root.key);
      }

      printNode(root.right, key);
    }
  }


  public static void main(String[] args) {

    MaxHeap heap = new MaxHeap();

    //Construct Min heap tree
    heap.insert(5);
    heap.insert(7);
    heap.insert(4);
    heap.insert(3);
    heap.insert(9);
    heap.insert(14);
    heap.insert(2);
    heap.insert(1);
    heap.insert(6);
    heap.insert(11);


    /*After insert element*/

    /*
               14
             /    \
            11      9
          /   \    /  \
         6     7  4    2
        / \   /
       1   3 5
    */

    int k = 10;
    heap.printNode(heap.root, k);

  }
}

 1 6 3 5 7 4 9 2

/*
  C# program
  Print all nodes less than a given value in a Max Heap
*/
using System;
//Tree node
public class Node {
	//Left and right child
	public Node left;
	public Node right;
	//Data value
	public int key;
	public Node(int key) {
		this.key = key;
		left = null;
		right = null;
	}
}
public class MaxHeap {
	//This is use to store information of number of nodes in Max heap
	public int size;
	public Node root;
	public MaxHeap() {
		root = null;
		size = 0;
	}
	//Get height of insert new node
	public int insertHeight() {
		int i = 1;
		int sum = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	public void swapNode(Node first, Node second) {
		int key = first.key;
		first.key = second.key;
		second.key = key;
	}
	//Arrange node key
	public void arrangeNode(Node root) {
		if (root.left != null && root.left.key > root.key) {
			swapNode(root, root.left);
		}
		if (root.right != null && root.right.key > root.key) {
			swapNode(root, root.right);
		}
	}
	public Boolean addNode(Node root, int height, int level, int key) {
		if (level >= height) {
			return false;
		}
		if (root != null) {
			if (level - 1 == height && root.left == null || root.right == null) {
				if (root.left == null) {
					root.left = new Node(key);
				} else {
					root.right = new Node(key);
				}
				arrangeNode(root);
				return true;
			}
			if (addNode(root.left, height, level + 1, key) || addNode(root.right, height, level + 1, key)) {
				arrangeNode(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	public void insert(int key) {
		//Test case

		if (root == null) {
			root = new Node(key);
		} else
		if (root.left == null) {
			root.left = new Node(key);
			arrangeNode(root);
		} else
		if (root.right == null) {
			root.right = new Node(key);
			arrangeNode(root);
		} else {
			int height = insertHeight();
			addNode(root, height, 0, key);
		}
		this.size++;
	}
	public void printNode(Node root, int key) {
		if (root != null) {
			printNode(root.left, key);
			if (root.key < key) {
				Console.Write(" " + root.key);
			}
			printNode(root.right, key);
		}
	}
	public static void Main(String[] args) {
		MaxHeap heap = new MaxHeap();
		heap.insert(5);
		heap.insert(7);
		heap.insert(4);
		heap.insert(3);
		heap.insert(9);
		heap.insert(14);
		heap.insert(2);
		heap.insert(1);
		heap.insert(6);
		heap.insert(11);
		/*After insert element*/
		/*
		               14
		             /    \
		            11      9
		          /   \    /  \
		         6     7  4    2
		        / \   /
		       1   3 5
		    */
		int k = 10;
		heap.printNode(heap.root, k);
	}
}

 1 6 3 5 7 4 9 2

<?php
/*
  Php program
  Print all nodes less than a given value in a Max Heap
*/
//Tree node
class Node {
  
	//Left and right child
	public $left;
	public $right;
	//Data value
	public $key;

	function __construct($key) {
		$this->key = $key;
		$this->left = null;
		$this->right = null;
	}
}
class MaxHeap {
	//This is use to store information of number of nodes in Max heap

	public $size;
	public $root;

	function __construct() {
		$this->root = null;
		$this->size = 0;
	}
	//Get height of insert new node

	public 	function insertHeight() {
		$i = 1;
		$sum = 0;
		while ($this->size > $sum + (1 << $i)) {
			$sum += (1 << $i);
			$i++;
		}
		return $i;
	}
	public 	function swapNode($first, $second) {
		$key = $first->key;
		$first->key = $second->key;
		$second->key = $key;
	}
	//Arrange node key
	public 	function arrangeNode($root) {
		if ($root->left != null && $root->left->key > $root->key) {
			$this->swapNode($root, $root->left);
		}
		if ($root->right != null && $root->right->key > $root->key) {
			$this->swapNode($root, $root->right);
		}
	}
	public 	function addNode($root, $height, $level, $key) {
		if ($level >= $height) {
			return false;
		}
		if ($root != null) {
			if ($level - 1 == $height && $root->left == null || $root->right == null) {
				if ($root->left == null) {
					$root->left = new Node($key);
				} else {
					$root->right = new Node($key);
				}
				$this->arrangeNode($root);
				return true;
			}
			if ($this->addNode($root->left, $height, $level + 1, $key) || 
                $this->addNode($root->right, $height, $level + 1, $key)) {
				//Check effect of new inserted node
				$this->arrangeNode($root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	public 	function insert($key) {
		//Test case
		if ($this->root == null) {
			$this->root = new Node($key);
		} 
        else if ($this->root->left == null) {
			$this->root->left = new Node($key);
			$this->arrangeNode($this->root);
		} 
      	else if ($this->root->right == null) {
			$this->root->right = new Node($key);
			$this->arrangeNode($this->root);
		} else {
			$height = $this->insertHeight();
			$this->addNode($this->root, $height, 0, $key);
		}
		$this->size++;
	}
	public 	function printNode($root, $key) {
		if ($root != null) {
			$this->printNode($root->left, $key);
			if ($root->key < $key) {
				//When element is less than of given key value

				echo(" ". $root->key);
			}
			$this->printNode($root->right, $key);
		}
	}
}

function main() {
	$heap = new MaxHeap();
	//Construct Min heap tree

	$heap->insert(5);
	$heap->insert(7);
	$heap->insert(4);
	$heap->insert(3);
	$heap->insert(9);
	$heap->insert(14);
	$heap->insert(2);
	$heap->insert(1);
	$heap->insert(6);
	$heap->insert(11);
	/*After insert element*/
	/*
	               14
	             /    \
	            11      9
	          /   \    /  \
	         6     7  4    2
	        / \   /
	       1   3 5
	    */
	$k = 10;
	$heap->printNode($heap->root, $k);

}
main();

 1 6 3 5 7 4 9 2

/*
  Node Js program
  Print all nodes less than a given value in a Max Heap
*/
//Tree node
class Node {

	constructor(key) {
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
class MaxHeap {

	constructor() {
		this.root = null;
		this.size = 0;
	}
	//Get height of insert new node
	insertHeight() {
		var i = 1;
		var sum = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}

		return i;
	}
	swapNode(first, second) {
		var key = first.key;
		first.key = second.key;
		second.key = key;
	}

	//Arrange node key
	arrangeNode(root) {
		if (root.left != null && root.left.key > root.key) {
			this.swapNode(root, root.left);
		}

		if (root.right != null && root.right.key > root.key) {
			this.swapNode(root, root.right);
		}
	}
	addNode(root, height, level, key) {
		if (level >= height) {
			return false;
		}

		if (root != null) {
			if (level - 1 == height && root.left == null || root.right == null) {
				if (root.left == null) {
					root.left = new Node(key);
				} else {
					root.right = new Node(key);
				}
				this.arrangeNode(root);
				return true;
			}

			if (this.addNode(root.left, height, level + 1, key) || 
                this.addNode(root.right, height, level + 1, key)) {
				//Check effect of new inserted node
				this.arrangeNode(root);
				return true;
			}
		}

		return false;
	}

	//Handles the request to new inserting node
	insert(key) {
		//Test case

		if (this.root == null) {
			this.root = new Node(key);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(key);
			this.arrangeNode(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(key);
			this.arrangeNode(this.root);
		} else {
			var height = this.insertHeight();
			this.addNode(this.root, height, 0, key);
		}
		this.size++;
	}
	printNode(root, key) {
		if (root != null) {
			this.printNode(root.left, key);
			if (root.key < key) {
				//When element is less than of given key value

				process.stdout.write(" " + root.key);
			}
			this.printNode(root.right, key);
		}
	}
}

function main(args) {
	var heap = new MaxHeap();
	//Construct Min heap tree
	heap.insert(5);
	heap.insert(7);
	heap.insert(4);
	heap.insert(3);
	heap.insert(9);
	heap.insert(14);
	heap.insert(2);
	heap.insert(1);
	heap.insert(6);
	heap.insert(11);
	/*After insert element*/
	/*
	               14
	             /    \
	            11      9
	          /   \    /  \
	         6     7  4    2
	        / \   /
	       1   3 5
	    */
	var k = 10;
	heap.printNode(heap.root, k);
}

main();

 1 6 3 5 7 4 9 2

#  Python 3 program
#  Print all nodes less than a given value in a Max Heap

# Tree node
class Node :

	def __init__(self, key) :
		self.key = key
		self.left = None
		self.right = None
	

class MaxHeap :
	def __init__(self) :
		self.root = None
		self.size = 0
	 # Get height of insert new node
	def insertHeight(self) :
		i = 1
		sum = 0
		while (self.size > sum + (1 << i)) :
			sum += (1 << i)
			i += 1
		
		return i
	
	def swapNode(self, first, second) :
		key = first.key
		first.key = second.key
		second.key = key
	 # Arrange node key
	def arrangeNode(self, root) :
		if (root.left != None and root.left.key > root.key) :
			self.swapNode(root, root.left)
		
		if (root.right != None and root.right.key > root.key) :
			self.swapNode(root, root.right)
		
	
	def addNode(self, root, height, level, key) :
		if (level >= height) :
			return False
		
		if (root != None) :
			if (level - 1 == height and root.left == None or root.right == None) :
				if (root.left == None) :
					root.left = Node(key)
				else :
					root.right = Node(key)
				
				self.arrangeNode(root)
				return True
			
			if (self.addNode(root.left, height, level + 1, key) or self.addNode(root.right, height, level + 1, key)) :
				# Check effect of new inserted node
				self.arrangeNode(root)
				return True
			
		
		return False
	 # Handles the request to new inserting node
	def insert(self, key) :
		# Test case

		if (self.root == None) :
			self.root = Node(key)
		elif (self.root.left == None) :
			self.root.left = Node(key)
			self.arrangeNode(self.root)
		elif (self.root.right == None) :
			self.root.right = Node(key)
			self.arrangeNode(self.root)
		else :
			height = self.insertHeight()
			self.addNode(self.root, height, 0, key)
		
		self.size += 1
	
	def printNode(self, root, key) :
		if (root != None) :
			self.printNode(root.left, key)
			if (root.key < key) :
				print(" ", root.key, end = "")
			
			self.printNode(root.right, key)
		
	

def main() :
	heap = MaxHeap() # Construct Min heap tree
	heap.insert(5)
	heap.insert(7)
	heap.insert(4)
	heap.insert(3)
	heap.insert(9)
	heap.insert(14)
	heap.insert(2)
	heap.insert(1)
	heap.insert(6)
	heap.insert(11)
	#
	#               14
	#             /    \
	#            11      9
	#          /   \    /  \
	#         6     7  4    2
	#        / \   /
	#       1   3 5
	#    
	
	#After insert element
	 
	#
	#               14
	#             /    \
	#            11      9
	#          /   \    /  \
	#         6     7  4    2
	#        / \   /
	#       1   3 5
	#    
	

	k = 10
	heap.printNode(heap.root, k)


if __name__ == "__main__":
	main()

  1  6  3  5  7  4  9  2

#  Ruby program
#  Print all nodes less than a given value in a Max Heap

# Tree node
class Node 
    # Define the accessor and reader of class Node
    attr_reader :left, :right, :key
    attr_accessor :left, :right, :key
	def initialize(key) 
		self.key = key
		@left = nil
		@right = nil
	end
end

class MaxHeap 
  	# Define the accessor and reader of class MaxHeap
	# size is use to store information of number of nodes in Max heap
    attr_reader :size, :root
    attr_accessor :size, :root
	def initialize() 
		@root = nil
		@size = 0
	end
	# Get height of insert new node
	def insertHeight() 
		i = 1
		sum = 0
		while (self.size > sum + (1 << i)) 
			sum += (1 << i)
			i += 1
		end
		return i
	end
	def swapNode(first, second) 
		key = first.key
		first.key = second.key
		second.key = key
	end
	# Arrange node key
	def arrangeNode(root) 
		if (root.left != nil && root.left.key > root.key) 
			self.swapNode(root, root.left)
		end
		if (root.right != nil && root.right.key > root.key) 
			self.swapNode(root, root.right)
		end
	end
	def addNode(root, height, level, key) 
		if (level >= height) 
			return false
		end
		if (root != nil) 
			if (level - 1 == height && root.left == nil || root.right == nil) 
				if (root.left == nil) 
					root.left = Node.new(key)
				else 
					root.right = Node.new(key)
				end
				self.arrangeNode(root)
				return true
			end
			if (self.addNode(root.left, height, level + 1, key) || self.addNode(root.right, height, level + 1, key)) 
				 # Check effect of new inserted node
				self.arrangeNode(root)
				return true
			end
		end
		return false
	end
	 # Handles the request to new inserting node
	def insert(key) 
		 # Test case

		if (@root == nil) 
			@root = Node.new(key)
		elsif (@root.left == nil) 
			@root.left = Node.new(key)
			self.arrangeNode(@root)
		elsif (@root.right == nil) 
			@root.right = Node.new(key)
			self.arrangeNode(@root)
		else 
			height = self.insertHeight()
			self.addNode(@root, height, 0, key)
		end
		self.size += 1
	end
	def printNode(root, key) 
		if (root != nil) 
			self.printNode(root.left, key)
			if (root.key < key) 
				 # When element is less than of given key value

				print(" ", root.key)
			end
			self.printNode(root.right, key)
		end
	end
end
def main() 
	heap = MaxHeap.new()
	 # Construct Min heap tree
	heap.insert(5)
	heap.insert(7)
	heap.insert(4)
	heap.insert(3)
	heap.insert(9)
	heap.insert(14)
	heap.insert(2)
	heap.insert(1)
	heap.insert(6)
	heap.insert(11)
	#After insert element
	 
	#
	#               14
	#             /    \
	#            11      9
	#          /   \    /  \
	#         6     7  4    2
	#        / \   /
	#       1   3 5
	#    
	
	k = 10
	heap.printNode(heap.root, k)
end


main()

 1 6 3 5 7 4 9 2

/*
  Scala program
  Print all nodes less than a given value in a Max Heap
*/
//Tree node
class Node(var left: Node,
	var right: Node,
		var key: Int) {
	def this(key: Int) {
		this(null,null,key);
	}
} 
class MaxHeap (var size: Int, var root: Node){

	def this() {
		this(0,null);
	}
	//Get height of insert new node
	def insertHeight(): Int = {
		var i: Int = 1;
		var sum: Int = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	def swapNode(first: Node, second: Node): Unit = {
		var key: Int = first.key;
		first.key = second.key;
		second.key = key;
	}
	//Arrange node key
	def arrangeNode(root: Node): Unit = {
		if (root.left != null && root.left.key > root.key) {
			this.swapNode(root, root.left);
		}
		if (root.right != null && root.right.key > root.key) {
			this.swapNode(root, root.right);
		}
	}
	def addNode(root: Node, height: Int, level: Int, key: Int): Boolean = {
		if (level >= height) {
			return false;
		}
		if (root != null) {
			if (level - 1 == height && root.left == null || root.right == null) {
				if (root.left == null) {
					root.left = new Node(key);
				} else {
					root.right = new Node(key);
				}
				this.arrangeNode(root);

				return true;
			}
			if (this.addNode(root.left, height, level + 1, key) || 
                this.addNode(root.right, height, level + 1, key)) {
				//Check effect of new inserted node
				this.arrangeNode(root);

				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	def insert(key: Int): Unit = {
		//Test case

		if (this.root == null) {
			this.root = new Node(key);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(key);
			this.arrangeNode(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(key);
			this.arrangeNode(this.root);
		} else {
			val height: Int = this.insertHeight();
			this.addNode(this.root, height, 0, key);
		}
		this.size += 1;
	}
	def printNode(root: Node, key: Int): Unit = {
		if (root != null) {
			this.printNode(root.left, key);

			if (root.key < key) {
				//When element is less than of given key value
				print(" " + root.key);
			}
			this.printNode(root.right, key);
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val heap: MaxHeap = new MaxHeap();

		//Construct Min heap tree
		heap.insert(5);
		heap.insert(7);
		heap.insert(4);
		heap.insert(3);
		heap.insert(9);
		heap.insert(14);
		heap.insert(2);
		heap.insert(1);
		heap.insert(6);
		heap.insert(11);

		/*After insert element*/
		/*
		               14
		             /    \
		            11      9
		          /   \    /  \
		         6     7  4    2
		        / \   /
		       1   3 5
		    */
		var k: Int = 10;
		heap.printNode(heap.root, k);
	}
}

 1 6 3 5 7 4 9 2

/*
  Swift program
  Print all nodes less than a given value in a Max Heap
*/
//Tree node
class Node {
	var left: Node? ;
	var right: Node? ;
	var key: Int;
	init(_ key: Int) {
		self.key = key;
		left = nil;
		right = nil;
	}
}
class MaxHeap {
	var size: Int;
	var root: Node? ;
	init() {
		root = nil;
		size = 0;
	}
	//Get height of insert new node
	func insertHeight() -> Int {
		var i = 1;
		var sum = 0;
		while (self.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	func swapNode(_ first: Node? , _ second : Node? ) {
		let key = first!.key;
		first!.key = second!.key;
		second!.key = key;
	}
	//Arrange node key
	func arrangeNode(_ root: Node? ) {
		if (root!.left != nil && root!.left!.key > root!.key) {
			self.swapNode(root, root!.left);
		}
		if (root!.right != nil && root!.right!.key > root!.key) {
			self.swapNode(root, root!.right);
		}
	}
	func addNode(_ root: Node? , _ height : Int, _ level: Int, _ key: Int) -> Bool {
		if (level >= height) {
			return false;
		}
		if (root != nil) {
			if (level - 1 == height && root!.left == nil || root!.right == nil) {
				if (root!.left == nil) {
					root!.left = Node(key);
				} else {
					root!.right = Node(key);
				}
				self.arrangeNode(root);
				return true;
			}
			if (self.addNode(root!.left, height, level + 1, key) || 
                self.addNode(root!.right, height, level + 1, key)) {
				//Check effect of new inserted node
				self.arrangeNode(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	func insert(_ key: Int) {
		//Test case

		if (root == nil) {
			root = Node(key);
		} else
		if (root!.left == nil) {
			root!.left = Node(key);
			self.arrangeNode(root);
		} else
		if (root!.right == nil) {
			root!.right = Node(key);
			self.arrangeNode(root);
		} else {
			let height = self.insertHeight();
			let _ = self.addNode(root, height, 0, key);
		}
		self.size += 1;
	}
	func printNode(_ root: Node? , _ key : Int) {
		if (root != nil) {
			self.printNode(root!.left, key);
			if (root!.key < key) {
				print(" ", root!.key, terminator: "");
			}
			self.printNode(root!.right, key);
		}
	}
}
func main() {
	let heap = MaxHeap();
	//Construct Min heap tree
	heap.insert(5);
	heap.insert(7);
	heap.insert(4);
	heap.insert(3);
	heap.insert(9);
	heap.insert(14);
	heap.insert(2);
	heap.insert(1);
	heap.insert(6);
	heap.insert(11);
	/*After insert element*/
	/*
	               14
	             /    \
	            11      9
	          /   \    /  \
	         6     7  4    2
	        / \   /
	       1   3 5
	    */
	let k = 10;
	heap.printNode(heap.root, k);
}
main();

  1  6  3  5  7  4  9  2

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the Max Heap. This is because each node is visited exactly once during the traversal, and the operations performed at each node take constant time. Therefore, the time complexity is linear with respect to the number of nodes in the Max Heap.