Print binary tree in level order

Question 17. Print the nodes of a binary tree in level order


To print the nodes of the binary tree in level order, we start with the root node and then print the child nodes in each level from left to right. Consider the binary tree below

The level order printing will result in the following output: ABCDEFG. To achieve this we make use of a queue and use the following strategy:

1. Add the root node to the queue

2. Remove the head element of the queue and print it. Then add the children of the removed element back to the queue. Repeat step-2 till the queue becomes empty.

C/C++


/*
root: root node of the tree 
q: queue that helps in printing in level order
*/
void print_level_order(struct node *root, queue<struct node*>& q)
{
	struct node *n;
	int num_nodes_in_cur_level, num_nodes_in_next_level;

	if (!root)
		return;

	/*Add the root node to the empty queue*/
	q.push(root);
	num_nodes_in_cur_level = 1;
	num_nodes_in_next_level = 0;

	/*Process the nodes in the queue in Breadth First manner*/
	while (!q.empty()) {

		/*Remove the node at the head of the queue*/
		n = q.front();
		q.pop();

		print_data(n->data); /*print the data in the node*/

		/*Add the left child to the end of the queue*/
		if (n->left) {
			q.push(n->left);
			num_nodes_in_next_level++;
		}

		/*Add the right child to the end of the queue*/
		if (n->right) {
			q.push(n->right);
			num_nodes_in_next_level++;
		}

		num_nodes_in_cur_level--;

		/*go to next line, if all nodes in current level are processed*/
		if (num_nodes_in_cur_level == 0) {
			cout << endl;
			num_nodes_in_cur_level = num_nodes_in_next_level;
			num_nodes_in_next_level = 0;
		}
	}
}



Java


/*
root: root node of the tree 
q: queue used for printing the tree 
*/
public static void printLevelOrder(TreeNode root, Queue<TreeNode> q) {
	if (root == null)
		return;

	/*Add the root node to the empty queue*/
	q.add(root);
	int numNodesInCurLevel = 1;
	int numNodesInNextLevel = 0;

	/*Process the nodes in the queue in Breadth First manner*/
	while (!q.isEmpty()) {

		/*Remove the node at the head of the queue*/
		TreeNode n = q.remove();

		printData(n.data); /*print the data in the node*/

		/*Add the left child to the queue*/
		if (n.left != null) {
			q.add(n.left);
			numNodesInNextLevel++;
		}

		/*Add the right child to the queue*/
		if (n.right != null) {
			q.add(n.right);
			numNodesInNextLevel++;
		}

		numNodesInCurLevel--;

		/*go to next line, if all nodes in current level are processed*/
		if (numNodesInCurLevel == 0) {
			System.out.println();
			numNodesInCurLevel = numNodesInNextLevel;
			numNodesInNextLevel = 0;
		}
	}
}



Python


#root: root node of the tree 
#q: Python Queue object used for printing the tree
@staticmethod
def print_level_order(root, q):
	if (not root):
		return

	#Add the root node to the empty queue
	q.put(root)
	num_nodes_in_cur_level = 1
	num_nodes_in_next_level = 0

	#Process the nodes in the queue in Breadth First manner
	while (not q.empty()) :
		#Remove the node at the head of the queue
		n = q.get()

		TreeNode.print_data(n.data) #print the data in the node

		#Add the left child to the queue
		if (n.left) :
			q.put(n.left)
			num_nodes_in_next_level += 1
		
		#Add the right child to the queue
		if (n.right) :
			q.put(n.right)
			num_nodes_in_next_level += 1
		
		num_nodes_in_cur_level = num_nodes_in_cur_level - 1

		#go to next line, if all nodes in current level are processed
		if (num_nodes_in_cur_level == 0) :
			print('')
			num_nodes_in_cur_level = num_nodes_in_next_level
			num_nodes_in_next_level = 0
		



Find if a binary tree is a binary search tree

Question 16. Find if a binary tree is a binary search tree


The initial approach that comes to mind is to check if the left child node is smaller than the parent node and the right child node is greater than the parent node for all the nodes in the tree. However this solution will not work as shown in the binary tree above. Every node satisfies the condition that the left child is smaller than the parent and the right child is greater than the parent. But the tree is still not a binary search tree since node 9 is incorrect. To correctly find out if a tree is a binary search tree, we should traverse the tree in-order and check if the nodes are present in ascending order

C/C++


/*cur_node: current node whose left and right sub-trees need to be checked
prev_node_pp: the in-order predecessor of cur_node
Return value: 1 if the tree is a binary search tree, 0 otherwise
*/
int is_bst(struct node *cur_node, struct node ** prev_node_pp)
{
	if (!cur_node)
		return 1;

	/*Check if the left sub-tree is a BST*/
	if (!is_bst(cur_node->left, prev_node_pp)) 
		return 0;

	/*If data in cur_node is <= to previous node then it is not a BST*/
	if (*prev_node_pp && cur_node->data <= (*prev_node_pp)->data)
		return 0;

	/*Update previous node to current node*/
	*prev_node_pp = cur_node;

	/*Check if the right sub-tree is a BST*/
	return is_bst(cur_node->right, prev_node_pp); 
}



Java


/*curNode: current node 
prevNodeArray: in-order predecessor of curNode is present in prevNodeArray[0]
Return value: true if the tree is a binary search tree, false otherwise
*/
public static boolean isBst(TreeNode curNode, TreeNode[] prevNodeArray)  {
	if (curNode == null)
		return true;

	/*Check if the left sub-tree is a BST*/
	if (!isBst(curNode.left, prevNodeArray)) 
		return false;

	/*If data in curNode is <= previous node then it is not a BST*/
	TreeNode prevNode = prevNodeArray[0];
	if (prevNode != null && curNode.data <= prevNode.data)
		return false;

	/*Update previous node to current node*/
	prevNodeArray[0] = curNode;

	/*Check if the right sub-tree is a BST*/
	return isBst(curNode.right, prevNodeArray); 
} 



Python


#cur_node: current node 
#prev_node_list: prev_node_list[0] has in-order predecessor of cur_node 
#Return values: True if the tree is a binary search tree, False otherwise
@staticmethod
def is_bst(cur_node, prev_node_list):
	if (not cur_node):
		return True

	#Check if the left sub-tree is a BST
	if (not TreeNode.is_bst(cur_node.left, prev_node_list)): 
		return False

	#If data in cur_node is <= previous node then it is not a BST
	prev_node = prev_node_list[0]
	if (prev_node and cur_node.data <= prev_node.data):
		return False

	#Update previous node to current node
	prev_node_list[0] = cur_node

	#Check if the right sub-tree is a BST
	return TreeNode.is_bst(cur_node.right, prev_node_list)



Is binary tree balanced

Question 15. Find if a binary tree is balanced


A binary tree is balanced if at every node in the tree, the absolute difference between the height of the left-subtree and the height of the right sub-tree doesn’t exceed 1. To solve the problem we recursively traverse the tree and calculate the height of the nodes in a bottom up manner. If at any node, the difference between the height of the left and right sub-trees exceeds 1, we report that the tree is unbalanced.

C/C++


/*cur_node: node of the binary tree being checked
height: height of the current node is returned here
Return value: 1 if the tree is balanced, 0 otherwise
*/
int is_balanced(struct node *cur_node, int *height)
{
	int is_left_balanced, is_right_balanced;
	int left_height, right_height;

	if (!cur_node) {
		*height = 0;
		return 1;
	}

	is_left_balanced = is_balanced(cur_node->left, &left_height);
	is_right_balanced = is_balanced(cur_node->right, &right_height);

	if (!is_left_balanced || !is_right_balanced)
		return 0;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (abs(left_height - right_height) > 1)
		return 0;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	*height = max(left_height, right_height) + 1;

	return 1;	
}



Java


/*curNode: node of the binary tree being checked
height: height of the curNode is returned here
Return value: true if the tree is balanced, false otherwise
*/
public static boolean isBalanced(TreeNode curNode, Int height) {
	Int leftHeight = new Int();
	Int rightHeight = new Int();

	if (curNode == null) {
		height.value = 0;
		return true;
	}


	boolean isLeftBalanced = isBalanced(curNode.left, leftHeight);
	boolean isRightBalanced = isBalanced(curNode.right, rightHeight);

	if (!isLeftBalanced || !isRightBalanced)
		return false;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (Math.abs(leftHeight.value - rightHeight.value) > 1)
		return false;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	height.value = Math.max(leftHeight.value, rightHeight.value) + 1;

	return true;	
}



Python


#cur_node: node of the binary tree being checked
#Return values: 1. True if the tree is balanced, False otherwise
#		2. height of the cur_node is also returned
@staticmethod
def is_balanced(cur_node) :
	if (not cur_node) :
		height = 0
		return True, height
	
	is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
	is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

	#To get the height of the current node, we find the maximum of the  
	#left subtree height and the right subtree height and add 1 to it
	height = max(left_height, right_height) + 1

	if (not is_left_balanced or not is_right_balanced):
		return False, height

	#If the difference between height of left subtree and height of
	#right subtree is more than 1, then the tree is unbalanced
	if (abs(left_height - right_height) > 1):
		return False, height
	
	return True, height	



Is binary tree symmetric

Question 14. Find if a binary tree is symmetric


A binary tree is symmetric, if the left sub-tree of each node is a mirror image of the right sub-tree. An example of a symmetric binary tree is given below

C/C++


int compare_nodes ( struct node *n1, struct node *n2) {
	if (!n1 && !n2)  /*If both the nodes are NULL */
		return 1;  /* return symmetric*/
	
	if ( (n1 && !n2) || (!n1 && n2)) /*If one node is NULL and other is not*/
		return 0; /*return not symmetric*/
	
	if (n1->data != n2->data) /*If data of two nodes don't match */
		return 0; /* return not symmetric */
		
	if (!compare_nodes (n1->left, n2->right)) 
		return 0;
	
	if (!compare_nodes (n1->right, n2->left)) 
		return 0;
	
	return 1; /*Return symmetric*/
}

/*Returns 1 if the tree is symmetric, 0 otherwise*/
int is_symmetric(struct node * root) {
	if (!root)
		return 1;
	
	return compare_nodes(root->left, root->right);
} 


Java


public static boolean compareNodes ( TreeNode n1, TreeNode n2) {
	if (n1 == null && n2 == null)  /*If both the nodes are null */
		return true;  /* return symmetric*/

	/*If one node is null and the other is not null*/
	if ( (n1 != null && n2 == null) || (n1 == null && n2 != null))  
		return false; /*return not symmetric*/

	if (n1.data != n2.data) /*If data of two nodes don't match */
		return false; /* return not symmetric */
	
	if (!compareNodes (n1.left, n2.right)) 
		return false;

	if (!compareNodes (n1.right, n2.left))
		return false;

	return true; /*Return symmetric*/
}

/*Returns true if the tree is symmetric, false otherwise*/
public static boolean isSymmetric(TreeNode root) {
	if (root == null)
		return true;

	return compareNodes(root.left, root.right);
}



Python


@staticmethod
def compare_nodes(n1, n2): 
	if (not n1 and not n2):  #If both the nodes are None
		return True  # return symmetric

	#If one node is None and the other is not None
	if ( (n1 and not n2) or (not n1 and n2)):  
		return False #return not symmetric

	if (n1.data != n2.data): #If data of two nodes don't match
		return False # return not symmetric 
	
	if (not TreeNode.compare_nodes(n1.left, n2.right)): 
		return False

	if (not TreeNode.compare_nodes(n1.right, n2.left)): 
		return False

	return True #Return symmetric


@staticmethod
#Returns True if the tree is symmetric, False otherwise
def is_symmetric(root): 
	if (not root):
		return True

	return TreeNode.compare_nodes(root.left, root.right) 



Mirror image of a binary tree

Question 13. Convert a binary tree into its mirror image


An example of a binary tree and its mirror image is shown below.

So to convert the binary tree to its mirror image, the left child and the right child of each node in the tree should be swapped

C/C++


/*
cur_node: current node of the tree whose mirror image should be computed
*/
void compute_mirror_image(struct node *cur_node) {
	struct node *temp_node;
	
	if (cur_node) {
		/*Swap the left child and right child of the current node*/
		temp_node = cur_node->left;
		cur_node->left = cur_node->right;
		cur_node->right = temp_node;

		/*Recursively compute the mirror image */
		compute_mirror_image(cur_node->left);
		compute_mirror_image(cur_node->right);
	}
}


Java


/*
curNode: current node of the tree whose mirror image should be computed
*/
public static void computeMirrorImage(TreeNode curNode) {
	if (curNode != null) {
		/*Swap the left child and right child of the current node*/
		TreeNode tempNode = curNode.left;
		curNode.left = curNode.right;
		curNode.right = tempNode;

		/*Recursively compute the mirror image */
		computeMirrorImage(curNode.left);
		computeMirrorImage(curNode.right);
	}
}


Python


@staticmethod
#cur_node: current node of the tree whose mirror image should be computed
def compute_mirror_image(cur_node): 
	if (cur_node) :
		#Swap the left child and right child of the current node
		cur_node.left, cur_node.right = cur_node.right, cur_node.left


		#Recursively compute the mirror image 
		TreeNode.compute_mirror_image(cur_node.left)
		TreeNode.compute_mirror_image(cur_node.right)