# Introduction To

Binary Tree Data Structure

Binary Tree is a special type of data structure. In binary tree, every node can have a maximum of 2 children, which are known as Left child and Right Child. It is a method of placing and locating the records in a database, especially when all the data is known to be in random access memory (RAM).

# Course Structure

## Introduction

- Binary Tree | Set 1 (Introduction)
- Binary Tree | Set 2 (Properties)
- Binary Tree | Set 3 (Types of Binary Tree)
- Handshaking Lemma and Interesting Tree Properties
- Enumeration of Binary Trees
- Insertion in a Binary Tree in level order
- Deletion in a Binary Tree
- BFS vs DFS for Binary Tree
- Binary Tree (Array implementation)
- Continuous Tree
- Foldable Binary Trees
- Expression Tree
- Evaluation of Expression Tree
- Symmetric Tree (Mirror Image of itself)

## Self-Balancing BSTs

## Misc

- Applications of tree data structure
- Succinct Encoding of Binary Tree
- Custom Tree Problem
- Tree Isomorphism Problem
- Ways to color a skewed tree such that parent and child have different colors
- Write a program to Delete a Tree
- Delete leaf nodes with value as x
- Non-recursive program to delete an entire binary tree
- Write a program to Calculate Size of a tree | Recursion
- Iterative program to Calculate Size of a tree
- Write a Program to Find the Maximum Depth or Height of a Tree
- Height of binary tree considering even level leaves only
- Find Height of Binary Tree represented by Parent array
- Find height of a special binary tree whose leaf nodes are connected
- Diameter of a Binary Tree
- Diameter of a Binary Tree in O(n) [A new method]
- Possible edges of a tree for given diameter, height and vertices
- Deepest right leaf node in a binary tree | Iterative approach
- Sink Odd nodes in Binary Tree
- Depth of the deepest odd level node in Binary Tree
- Find depth of the deepest odd level leaf node
- Find the Deepest Node in a Binary Tree
- Deepest left leaf node in a binary tree | iterative approach
- Deepest left leaf node in a binary tree
- Find Minimum Depth of a Binary Tree
- Replace node with depth in a binary tree
- Maximum width of a binary tree
- Vertical width of Binary tree | Set 1
- Vertical width of Binary tree | Set 2
- Find if given vertical level of binary tree is sorted or not
- Check if a binary tree is sorted level-wise or not
- Bottom View of a Binary Tree
- Program to count leaf nodes in a binary tree
- Iterative program to count leaf nodes in a Binary Tree
- Count Non-Leaf nodes in a Binary Tree
- Count half nodes in a Binary tree (Iterative and Recursive)
- Count full nodes in a Binary tree (Iterative and Recursive)
- Connect Nodes at same Level (Level Order Traversal)
- Connect nodes at same level using constant extra space
- Connect nodes at same level
- Level with maximum number of nodes
- Largest value in each level of Binary Tree | Set-2 (Iterative Approach)
- Smallest value in each level of Binary Tree
- Get Level of a node in a Binary Tree
- Get level of a node in binary tree | iterative approach
- Find mirror of a given node in Binary tree
- Find largest subtree having identical left and right subtrees
- Find Count of Single Valued Subtrees
- Closest leaf to a given node in Binary Tree
- Find the closest leaf in a Binary Tree
- Iterative Search for a key ‘x’ in Binary Tree
- Given a binary tree, how do you remove all the half nodes?
- Swap Nodes in Binary tree of every k’th level
- Pairwise Swap leaf nodes in a binary tree
- Root to leaf paths having equal lengths in a Binary Tree
- Maximum Consecutive Increasing Path Length in Binary Tree
- Longest Path with Same Values in a Binary Tree
- Remove nodes on root to leaf paths of length < K
- Longest consecutive sequence in Binary tree
- Path length having maximum number of bends
- Number of turns to reach from one node to other in binary tree
- Create loops of even and odd values in a binary tree
- Find first non matching leaves in two binary trees
- Get maximum left node in binary tree
- Find a number in minimum steps
- Factor Tree of a given Number
- Number of full binary trees such that each node is product of its children
- Number of subtrees having odd count of even numbers
- Find distance from root to given node in a binary tree
- Find distance between two nodes of a Binary Tree
- Find right sibling of a binary tree with parent pointers
- Find next right node of a given key | Set 2
- Tilt of Binary Tree
- Top three elements in binary tree
- Find maximum (or minimum) in Binary Tree
- Extract Leaves of a Binary Tree in a Doubly Linked List
- Minimum no. of iterations to pass information to all nodes in the tree

## Traversals

- Tree Traversals (Inorder, Preorder and Postorder)
- Inorder Tree Traversal without Recursion
- Inorder Tree Traversal without recursion and without stack!
- Print Postorder traversal from given Inorder and Preorder traversals
- Find postorder traversal of BST from preorder traversal
- Find all possible binary trees with given Inorder Traversal
- Populate Inorder Successor for all nodes
- Inorder Successor of a node in Binary Tree
- Find n-th node of inorder traversal
- Find n-th node in Postorder traversal of a Binary Tree
- Level order traversal line by line | Set 3 (Using One Queue)
- Level order traversal with direction change after every two levels
- Reverse Level Order Traversal
- Reverse tree path
- Perfect Binary Tree Specific Level Order Traversal
- Perfect Binary Tree Specific Level Order Traversal | Set 2
- Reverse alternate levels of a perfect binary tree
- Morris traversal for Preorder
- Iterative Preorder Traversal
- Postorder traversal of Binary Tree without recursion and without stack
- Diagonal Traversal of Binary Tree
- Iterative diagonal traversal of binary tree
- Boundary Traversal of binary tree
- Density of Binary Tree in One Traversal
- Calculate depth of a full Binary tree from Preorder
- Number of Binary Trees for given Preorder Sequence length
- Modify a binary tree to get preorder traversal using right pointers only

## Construction & Conversion

- Construct Tree from given Inorder and Preorder traversals
- Construct a tree from Inorder and Level order traversals | Set 1
- Construct a complete binary tree from given array in level order fashion
- Construct Full Binary Tree from given preorder and postorder traversals
- Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
- Construct a special tree from given preorder traversal
- Construct Special Binary Tree from given Inorder traversal
- Construct Binary Tree from given Parent Array representation
- Construct a Binary Tree from Postorder and Inorder
- Prufer Code to Tree Creation
- If you are given two traversal sequences, can you construct the binary tree?
- Construct the full k-ary tree from its preorder traversal
- Construct Binary Tree from String with bracket representation
- Linked complete binary tree & its creation
- Convert a given Binary Tree to Doubly Linked List | Set 1
- Convert a given Binary Tree to Doubly Linked List | Set 2
- Convert a given Binary Tree to Doubly Linked List | Set 3
- Convert an arbitrary Binary Tree to a tree that holds Children Sum Property
- Convert left-right representation of a binary tree to down-right
- Convert a given tree to its Sum Tree
- Change a Binary Tree so that every node stores sum of all nodes in left subtree
- Convert a Binary Tree into its Mirror Tree
- Convert a Binary Tree into Doubly Linked List in spiral fashion
- Convert a tree to forest of even nodes
- Convert a given Binary tree to a tree that holds Logical AND property
- Convert Ternary Expression to a Binary Tree
- Flip Binary Tree
- Minimum swap required to convert binary tree to binary search tree

## n-ary Trees and LCA

## Checking & Printing

- Check for Children Sum Property in a Binary Tree
- Check sum of Covered and Uncovered nodes of Binary Tree
- Check if two nodes are cousins in a Binary Tree
- Check if all leaves are at same level
- Check if removing an edge can divide a Binary Tree in two halves
- Check if given Preorder, Inorder and Postorder traversals are of same tree
- Check if leaf traversal of two Binary Trees is same?
- Check if a given Binary Tree is SumTree
- Check whether a given binary tree is perfect or not
- Check whether a binary tree is a full binary tree or not
- Check whether a binary tree is a full binary tree or not | Iterative Approach
- Check if a given Binary Tree is height balanced like a Red-Black Tree
- Check if a binary tree is subtree of another binary tree | Set 2
- Check if a Binary Tree (not BST) has duplicate values
- Check if a Binary Tree contains duplicate subtrees of size 2 or more
- Check if two trees are Mirror
- Iterative method to check if two trees are mirror of each other
- Write Code to Determine if Two Trees are Identical
- Iterative function to check if two trees are identical
- Check for Symmetric Binary Tree (Iterative Approach)
- Check if there is a root to leaf path with given sequence
- Print middle level of perfect binary tree without finding height
- Print cousins of a given node in Binary Tree
- Given a binary tree, print out all of its root-to-leaf paths one per line.
- Print the longest leaf to leaf path in a Binary tree
- Print root to leaf paths without using recursion
- Print the nodes at odd levels of a tree
- Print all full nodes in a Binary Tree

## Summation

- Sum of all nodes in a binary tree
- Sum of all the parent nodes having child node x
- Find sum of all left leaves in a given Binary Tree
- Find sum of all right leaves in a given Binary Tree
- Find sum of all nodes of the given perfect binary tree
- Diagonal Sum of a Binary Tree
- Find if there is a pair in root to a leaf path with sum equals to root’s data
- Sum of nodes on the longest path from root to leaf node
- Remove all nodes which don’t lie in any path with sum>= k
- Find the maximum path sum between two leaves of a binary tree
- Find the maximum sum leaf to root path in a Binary Tree
- Maximum sum of nodes in Binary tree such that no two are adjacent
- Maximum sum from a tree with adjacent levels not allowed
- Print all k-sum paths in a binary tree
- Sum of heights of all individual nodes in a binary tree
- Subtree with given sum in a Binary Tree
- Count subtrees that sum up to a given value x
- Sum of nodes at maximum depth of a Binary Tree
- Difference between sums of odd level and even level nodes of a Binary Tree
- Maximum spiral sum in Binary Tree
- Sum of nodes at k-th level in a tree represented as string
- Sum of all leaf nodes of binary tree
- Sum of leaf nodes at minimum level
- Root to leaf path sum equal to a given number
- Sum of all the numbers that are formed from root to leaf paths
- Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)
- Vertical Sum in Binary Tree | Set 2 (Space Optimized)
- Find root of the tree where children id sum for every node is given
- Replace each node in binary tree with the sum of its inorder predecessor and successor
- Find largest subtree sum in a tree

## Longest Common Ancestor

- Lowest Common Ancestor in a Binary Tree | Set 1
- Lowest Common Ancestor in a Binary Tree | Set 2 (Using Parent Pointer)
- Lowest Common Ancestor in a Binary Tree | Set 3 (Using RMQ)
- Find distance between two nodes of a Binary Tree
- Print common nodes on path from root (or common ancestors)
- Maximum difference between node and its ancestor in Binary Tree
- Print the path common to the two paths from the root to the two given nodes
- Query for ancestor-descendant relationship in a tree
- Print path from root to a given node in a binary tree
- Print Ancestors of a given node in Binary Tree
- Kth ancestor of a node in binary tree | Set 2

## Segment Tree

## Misc

- Applications of tree data structure
- Succinct Encoding of Binary Tree
- Custom Tree Problem
- Tree Isomorphism Problem
- Ways to color a skewed tree such that parent and child have different colors
- Write a program to Delete a Tree
- Delete leaf nodes with value as x
- Non-recursive program to delete an entire binary tree
- Write a program to Calculate Size of a tree | Recursion
- Iterative program to Calculate Size of a tree
- Write a Program to Find the Maximum Depth or Height of a Tree
- Height of binary tree considering even level leaves only
- Find Height of Binary Tree represented by Parent array
- Find height of a special binary tree whose leaf nodes are connected
- Diameter of a Binary Tree
- Diameter of a Binary Tree in O(n) [A new method]
- Possible edges of a tree for given diameter, height and vertices
- Deepest right leaf node in a binary tree | Iterative approach
- Sink Odd nodes in Binary Tree
- Depth of the deepest odd level node in Binary Tree
- Find depth of the deepest odd level leaf node
- Find the Deepest Node in a Binary Tree
- Deepest left leaf node in a binary tree | iterative approach
- Deepest left leaf node in a binary tree
- Find Minimum Depth of a Binary Tree
- Replace node with depth in a binary tree
- Maximum width of a binary tree
- Vertical width of Binary tree | Set 1
- Vertical width of Binary tree | Set 2
- Find if given vertical level of binary tree is sorted or not
- Check if a binary tree is sorted level-wise or not
- Bottom View of a Binary Tree
- Program to count leaf nodes in a binary tree
- Iterative program to count leaf nodes in a Binary Tree
- Count Non-Leaf nodes in a Binary Tree
- Count half nodes in a Binary tree (Iterative and Recursive)
- Count full nodes in a Binary tree (Iterative and Recursive)
- Connect Nodes at same Level (Level Order Traversal)
- Connect nodes at same level using constant extra space
- Connect nodes at same level
- Level with maximum number of nodes
- Largest value in each level of Binary Tree | Set-2 (Iterative Approach)
- Smallest value in each level of Binary Tree
- Get Level of a node in a Binary Tree
- Get level of a node in binary tree | iterative approach
- Find mirror of a given node in Binary tree
- Find largest subtree having identical left and right subtrees
- Find Count of Single Valued Subtrees
- Closest leaf to a given node in Binary Tree
- Find the closest leaf in a Binary Tree
- Iterative Search for a key ‘x’ in Binary Tree
- Given a binary tree, how do you remove all the half nodes?
- Swap Nodes in Binary tree of every k’th level
- Pairwise Swap leaf nodes in a binary tree
- Root to leaf paths having equal lengths in a Binary Tree
- Maximum Consecutive Increasing Path Length in Binary Tree
- Longest Path with Same Values in a Binary Tree
- Remove nodes on root to leaf paths of length < K
- Longest consecutive sequence in Binary tree
- Path length having maximum number of bends
- Number of turns to reach from one node to other in binary tree
- Create loops of even and odd values in a binary tree
- Find first non matching leaves in two binary trees
- Get maximum left node in binary tree
- Find a number in minimum steps
- Factor Tree of a given Number
- Number of full binary trees such that each node is product of its children
- Number of subtrees having odd count of even numbers
- Find distance from root to given node in a binary tree
- Find distance between two nodes of a Binary Tree
- Find right sibling of a binary tree with parent pointers
- Find next right node of a given key | Set 2
- Tilt of Binary Tree
- Top three elements in binary tree
- Find maximum (or minimum) in Binary Tree
- Extract Leaves of a Binary Tree in a Doubly Linked List
- Minimum no. of iterations to pass information to all nodes in the tree