Queue

A queue is a linear data structure working on First In First Out policy. But some use cases can require different solutions. We can create different queue types with the same basic idea. This post describes more about them

A queue is a linear data structure which maintains the order in which the elements appear. You need to implement a queue, using two stacks such that it behaves in the same way. If you are unfamiliar with the queue data structure and the stack data structure, it would be a good idea to learn them before approaching this problem. Problem Statement: The basic crux of the problem is that you are to implement a queue and its operations using stacks. It may seem unnecessary in the beginning, as a …

Question: Given the root pointer to a binary tree, find the left view of the tree. Input: Sample Tree (Pointer to node 1 is given). Output: 1, 2, 4 At a single glance of the problem, we can understand that we need to perform a level order traversal on the tree. This is similar to finding the number of levels in a tree. At the start of each level, we just print the first element. This can be done with the algorithm below:- Time Complexity:- O(n) Space Complexity:- O(n) Ideone …

Question: Given the root pointer to a binary tree, find the sum of all its elements without using recursion. Input: Sample Tree (Pointer to node 1 is given). Output: Sum = 15 We discussed how to find the sum of all elements of a binary tree using recursion in this post. Given a binary tree, find the sum of all elements. If recursion seems tough to you , you can always go by the iterative approach and use Level Order Traversal of binary tree. While performing a level order traversal, …

Question: Given the root pointer to a binary tree, find the height. Input: Sample Tree (Pointer to node 1 is given). Output: 3 We discussed the recursive method to find the height of the binary tree in this post- Find the height of the binary tree The non-recursive method will definitely require the level order traversal technique. The level order traversal will traverse the above tree in following manner- 1 2, 3 4, 5 If we are able to keep a track for end of each level, we can easily …

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 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, 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 …