Trees

Question: Given the root pointer to a binary tree, find the number of full nodes. Input: Sample Tree (Pointer to node 1 is given). Find the number of full nodes. Output: Number of full nodes = 3 According to the definition, the set of all nodes with both left and right child are called as full nodes. In the above example, we have the nodes – 1. 2, 3 as full nodes. We can perform a level order traversal and count the number of nodes, who have their right child…

Question: Given the root pointer to a binary tree, find the number of leaves. Input: Sample Tree (Pointer to node 1 is given). Find the number of leaves. Output: Number of leaves = 4 According to the definition, the set of all nodes whose both left and right child are null, are known as leaf nodes. In the above example, we have the nodes – 7, 9, 5, 4 as the leaf nodes. We can perform a level order traversal and count the number of nodes, who have their right…

Question: Given the root pointer to a binary tree, find the deepest node. Input: Sample Tree (Pointer to node 1 is given). Output: 5 According to the definition, the deepest node in a binary tree is the last element in the binary tree while performing a level order traversal. In the above case, therefore we have “5” as the deepest node in the tree. We can simply follow a level order traversal approach to solve this problem. Just return the last element to get the deepest node. Here is the…

Question: Given the root pointer to a binary tree, find the height. Input: Sample Tree (Pointer to node 1 is given). Output: 3 The method we will learn relates to the same method we discussed in the post how to find the size of a binary tree – Find the size of a binary tree In the above post we applied a recursive approach because the tree follows a recursive property. Every node has the same property. It has a root value, a left pointer and a right pointer. This…

Question: Given the root pointer to a binary tree, delete the binary tree Input: Sample Tree (Pointer to node 1 is given). To delete a tree we must traverse all the nodes of the tree and delete them one by one. So which traversal should we use ? Inorder, Pre-order, Post-order or Level Order Traversal ? Before deleting he parent node, we should delete its child node first. We can therefore use post order traversal as it does the work without storing anything. We can delete three with other traversals…

Question: Given the root pointer to a binary tree, find its size. Input: Sample Tree (Pointer to node 1 is given). Find the size Output: Size = 7 We discussed how to find the size of a binary tree using the recursive method in this post:- Write an algorithm to find the size of a binary tree This technique involved recursion and the understanding can be a bit complicated. If you prefer to go through the iterative way, we can simple do a level order traversal on the tree. At…

Question: Given the root pointer to a binary tree, find its size. Input: Sample Tree (Pointer to node 1 is given). Find the size Output: Size = 7 The size of the binary tree is basically the number of nodes in a binary tree. Since, the tree follows a recursive approach we can easily solve this problem by recursion. We calculate the size of left and right sub-tree recursively, add 1 (current node) and return to its parent. The recursive implementation can be done as:- EXPLANATION CASE 1 : When…

Question: Given the root pointer to a binary tree, write a program to insert an element in it. Input: Sample Tree (Pointer to node 1 is given), Insert 7 Output: After insertion We are given a binary tree with random allocated values and the pointer to the root node is given. Since the given tree is a binary tree, we can insert the element wherever we want. The only property of binary tree is that every node can have a maximum of two children. So, to keep the tree leveled…

Question: Given the root pointer to a binary tree, find if an element is present in it. Input: Sample Tree (Pointer to node 1 is given), Search – 3 Output: Present We discussed how to find if an element exists in the binary tree in this post. Find if an element is present in a binary tree That involved recursion. If recursion seems difficult to you, we can even solve this problem with the help of level order traversal of binary tree. The property of level order traversal is that…

Question: Given the root pointer to a binary tree, find if an element is present in it. Input: Sample Tree (Pointer to node 1 is given), Search – 3 Output: Present One simple way of solving this problem is to find the element in the left sub-tree, in the right sub-tree, and in the root data. This approach can be easily implemented with recursion. This approach works because each node of the tree has 3 parts -> the root, the left and the right. What we do is we see…