In recursive dfs traversals (preorder, inorder and postorder), output depends on the order in which we process the root node. Algorithm is simple and easy to visualize! The critical question is: How do we implement these traversals without using recursion? The answer is: We use stack to simulate a recursive dfs traversal into an iterative dfs traversal.

There are three types of recursive tree traversals: preorder, inorder and postorder. This classification is based on the visit sequence of root node 1) Preorder traversal: root is visited first 2) Inorder traversal: root is visited after left subtree 3) Postorder traversal: root is visited last. These are also called depth first search or DFS traversal.

AVL Trees is a height-balanced BST named after its inventors, Adelson-Velsky and Landis. This is a variation of binary search trees, also known as self-balancing BST. The property of AVL Trees: The absolute difference of height between left and right subtree is at max 1, which could help us to perform bst operations in O(logn) time complexity.

A Fenwick tree is a data structure that efficiently updates elements and calculates prefix sums in an array. It takes O(logn) time for both updates and range sum queries. Fenwick tree is also called binary indexed tree (BIT), which was first described in the paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).

Heap is a complete binary tree structure where each node satisfies a heap property. We learn two types of heap data structure: 1) Max heap, which satisfies the max heap property, and 2) Min heap, which satisfies the min-heap property. We use heap data structures to implement priority queues and solve several coding problems efficiently.

Binary search tree (BST) is a sorted binary tree, where key stored in each node must satisfy the binary search tree property: 1) Keys in the left subtree ≤ Node key 2) Keys in the right subtree ≥ Node key 3) Both subtrees must be binary search trees. In this blog, we have discussed the key properties, operations and differences of BST with a hash table.

The root of the binary search tree and a key k is given. Write a program to insert key k into the binary search tree. Note: BST structure will change after the insertion. So we need to perform insertion in such a way that the BST property continues to hold. In this blog, we have discussed recursive and iterative implementations of insertion in BST.

We start searching from root node and traverse a path downward in binary search tree. For each node in the path, compare target key k with the node key. If equal, search is successful. If k < node key, go to the left subtree. Similarly, if k > node key, go to the right subtree. In this blog, we have discussed recursive and iterative implementations of searching in BST.

Level order traversal accesses nodes in level by level order. This is also called breadth first search or BFS traversal. Here we start processing from the root node, then process all nodes at the first level, then process all nodes at the second level, and so on. In other words, we explore all nodes at the current level before going to nodes at the next level.

Given the root of a binary tree, write a program to check whether tree is a valid binary search tree (BST) or not. To check valid bst, we verify bst property at each node: All node values in the left subtree are less than node’s value, all node values in the right subtree are greater than node’s value, and both subtrees are also binary search trees.

We know that a binary tree is a rooted tree in which each node has no more than two children. We can extend this definition to an n-ary tree. If a tree is rooted in which each node has no more than n children, it is called an n-ary tree. In other words, n ary trees are tree data structures with up to n children nodes for each node present in the tree.

Suffix trees are a compressed version of the trie that includes all of a string's suffixes. It can be used to solve many string problems that occur in text editing, free-text searches, etc. Some popular applications of suffix trees are string search, finding the longest repeated substring, finding the longest common substring, data compression, etc.

Binary tree is one of the simplest tree data structures where each node has at most two child nodes. In other words, a node in a binary tree can have 0 or 1 or 2 child nodes. In this blog, we have discussed: 1) Key terminologies 2) Types of binary tree 3) Properties of binary tree 4) Linked and array representation 5) Binary tree applications.

In this blog, we will learn how to use segment trees for efficient point and range updates. For point update query, update(idx, val), we need to increment element at index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For range update query, update(l, r, val), we increment all elements from index l to r from the original array by val.

A segment tree is a binary tree data structure such that each node stores information about a range. We use segment trees to efficiently answer multiple range queries on an array like range minimum, range maximum, range sum, etc. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time.

Given a root node of a binary tree, write a program to find the left view of the given binary tree. The left view of a binary tree is a group of nodes visible when viewed from the left side. In other words, the nodes in the left view will be the first node of each level. This is an excellent problem to learn problem-solving using DFS and BFS traversal.

Given the root of a BST and an integer k, write a program to find the kth largest value among all the nodes' values in the binary search tree. Note: This is an excellent problem to learn problem solving using recursive and iterative inorder traversal and data structure augmentation (storing extra information inside BST nodes for solving a problem).

Given the root of a binary search tree (BST), write a program to find the absolute minimum difference between the values of any two nodes in the tree. Here node values in the tree can be positive, negative, or zero. Note: This is an excellent problem to learn problem-solving using iterative and recursive inorder traversal of a binary tree.

Given the root node of a binary tree, write a program to find its height. The height or depth of a binary tree is equal to the count of nodes on the longest path from the root to leaf node, i.e., maximum number of nodes from the root to the most distant leaf. Note: This is an excellent problem to learn problem-solving using DFS and BFS traversal.

Given two binary trees, write a program to merge them into a single binary tree. We need to merge them such that if two nodes overlap then add them and put them into the new tree at the same position. Otherwise, put the non-NULL node in the new tree. Note: This is an excellent problem to learn problem solving using iterative and recursive preorder traversal.

Given a binary tree, find its minimum depth. The min depth of a binary tree is the number of nodes along the shortest path from root node down to the nearest leaf node. The path has to end on a leaf node. Note: An excellent problem to understand efficient problem solving using breadth-first search (BFS) when the solution node is nearest to the root node.