https://www.geeksforgeeks.

org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

https://www.geeksforgeeks.org/kth-largest-element-in-bst-when-modification-to-bst-is-not-all

https://www.techiedelight.com/determine-given-binary-tree-is-a-bst-or-not/

https://www.techiedelight.com/find-lowest-common-ancestor-lca-two-nodes-binary-tree/

https://www.techiedelight.com/calculate-height-binary-tree-iterative-recursive/

Q) Terminologies
1) Root Node :-
 First or topmost node of a tree.
 This node doesn’t have any parent node.

2) Sibling Node
 Nodes (x1,x2,..) which appear from the same parent x are called sibling nodes.

3) Leaf Node/Terminal Node/External Node

 This is the node which doesn’t have any child node.

4) Internal Node/Non Terminal Node

 This is the node which has atleast 1 child node
 Root Node is also a Internal Node only

Q) Depth of a Node,Ht. of a Node,Ht. of a Tree

1) Depth of a Node N
 Number of edges from root ‘R’ to that node ‘N’
 Depth of the Root ‘R’ is 0.

2) Height of a Node N
 Number of edges from node ‘N to the deepest leaf of it’s subtree
 Height of each leaf = 0.

3) Height of the Tree = Height of the Root

 No. of edges from in the path from root to the deepest leaf in the tree
 A Tree with only one node (i.e the root node) has height 0.

Q) Unlabelled Binary Tree

1) A binary tree is unlabeled if its nodes are not assigned any label
Q) Labelled Binary Tree

1) A binary tree is labeled if all its nodes are assigned a label.

Q) Table 1
 Max and Min no. of Nodes in some standard BT’s
 When ht. h of those BT’s is provided.

Max no. of Nodes (n m a x ) Min no. of Nodes (n m i n )

(for a given ht. h) (for a given ht. h)

Binary Tree nmax = 2h+1 - 1 n m i n = h+1

Full Binary Tree nmax = 2h+1 - 1 n m i n = 2h+1
Almost Complete BT nmax = 2h+1 - 1 nmin = 2h

Q) Table 2
 Max and Min height of some standard BT’s
 When no. of nodes n of those BT’s is provided.

Max ht (h m a x ) Min ht (h m i n )
(for given no. of nodes n) (for given no. of nodes n)
Binary Tree h m a x = [log 2 (n+1)] - 1 hmin = n - 1
Full Binary Tree h m a x = [log 2 (n+1)] - 1 h m i n = (n – 1)/2
Almost Complete BT h m a x = [log 2 (n+1)] - 1 h m i n = log 2 n

Q) Tree Traversals
Q) Basic Problems
Q) Find size of binary tree

Size of BT = no. of nodes in the binary tree = 1 + (size_of_left_subtree) + (size_of_right_subtre

 i.e No. of nodes in the left subtree of root (i.e Size of left Subtree) PLUS
 No. of nodes in the right subtree of root (i.e Size of right Subtree) PLUS
 1 (i.e count the root node itself)

int size (Node * node )

{
    if(root== NULL )
        return  0;
    
return  1 + size (root ->left ) + size (root ->right );
}

Q) Count the no. of leaf Nodes in a BT (Recursively)

Procedure:-
1) If Node x is NULL then return 0.
 if (x == NULL)  return 0;

2) If left and right child of Node x are NULL return 1.

 i.e if (x.left == NULL) && (x.right == NULL)  Return 1
 Bcoz then x is a Leaf Node

3) Else Calculate using the formula:-

 Leaf count of a Tree = Leaf count of Left Subtree + Leaf Count of Right Subtree

int leaf_count1(Node* x)
{
    if (x == nullptr)
        return 0;

    if ( (x->left == NULL) && (x->right == NULL) )
        return 1;

    return leaf_count1(x->left) + leaf_count1(x->right);
}

1) Since this program is similar to traversal of tree,

  time and space complexities will be same as Tree traversal

https://www.techiedelight.com/determine-given-binary-tree-is-a-bst-or-not/

Q) Determine whether a BT is a BST or not.

Greedy Algo :-
1) Traverse the tree,
 at every node check whether the node
 contains a value larger than the value at the left child
 and smaller than the value on the right child –
 Does not work for all cases

Actual Logic :-
1) So, the condition we need to check at each node is:
 If the node is the left child of its parent,
 it must be smaller than (or equal to) the parent,
 and it must pass down the value from its parent to its right subtree to make sure none of th
than the parent.

2) If the node is the right child of its parent,

 it must be larger than the parent,
 and it must pass down the value from its parent to its left subtree
to make sure none of the nodes in that subtree is lesser than the parent.

Ex1) Code
bool isBST(Node* x,int min_key, int max_key)
{
    if(x == NULL)
        return true;

    // If the range of current node's data (i.e x->data)doesnt lie b/w [min_key, max_key]
    // Then return false.
    if( (x->data < min_key) || (x->data > max_key) )
        return false;

    return isBST(x->left, min_key, x->data) &&
           isBST(x->right, x->data, max_key);
}

// Function to determine whether a given binary tree is a BST
void isBST(Node* root)
{
    if( isBST(root, INT_MIN, INT_MAX) ) 
    {
        printf("The tree is a BST.");
    }
    else 
    {
        printf("The tree is not a BST!");
    }
}

1) For root (i.e 6)

 Range = [min_key, max_key] = [-inf, inf]

2) For 2 :-
 Range = [min_key, max_key] = [-inf, 4]
 i.e xleft requires upper Bound
 Upper Bound = x  data

3) For 6 :-
 Range = [min_key, max_key] = [4, inf]
 i.e xright requires lower Bound
 Lower Bound = x  data

4) Time Complexity = O(n)

https://www.techiedelight.com/find-diagonal-sum-given-binary-tree/

Q) Print Left Diagonal Sum of a BT.

 Calculate the sum of all nodes for each diagonal havoing -ve slope.
 Assume that the left, right child of a node make 45 deg angle with the parent.
1) We can easily solve the problem using Hashing :-

2) Create a empty map m

 key  i t h diagonal.
 value  Maintains the sum of all nodes present in the current i t h diagonal.

// Perform preorder/postorder traversal (i.e perform DFS)
// And in the map m (Store the sum of all nodes) present in each and every left diags.
// In this case we are performing preorder traversal.
// We may also do postorder traversal.
void generateLeftDiagonalSum(Node* root, int diagonal, auto &m)
{
    // Base Case (Empty Tree)
    if(root == nullptr)
        return;

    m[diagonal] += root->data;

    // recur for the left subtree by increasing diagonal by 1
    generateDiagonalSum(root->left, diagonal+1, m);

    // recur for the left subtree with the same diagonal.
    generateDiagonalSum(root->right, diagonal, m);
}

// 
void printLeftDiagonalSum(Node* root)
{
    unordered_map<int, int> m;

    // traverse the tree in a preorder fashion and fill the map
    generateDiagonalSum(root, 0, m);
 
    // traverse the map and print the diagonal sum
    for (int i = 0; i < m.size(); i++) 
    {
        printf("\nDiagonal %d Sum = %d ",i,m[i]);
    }

Output :-

Diagonal 0 Sum = 10
Diagonal 1 Sum = 15
Diagonal 2 Sum = 11

Q) Convert BT to it’s mirror BT

 Same as inverting a BT.

1) Traverse the Binary tree in a post-order/pre-order fashion

2) For every node x encountered

 Swap it’s left, right child.
 i.e Swap x  left, x  right.

Ex1) Code
// Convert the given BT to it's mirror image.
// Do a DFS Traversal (i.e postorder/preorder traversal).
void convertToMirror(Node* root)
{
    // If Tree is empty (Base Case)
    if(root == nullptr)
        return;

    // convert left subtree
    convertToMirror(root->left);

    // convert right subtree
    convertToMirror(root->right);

    // swap left subtree with right subtree
    swap(root->left, root->right);

1) Time Complexity:- O(n)

 n = Number of nodes in the binary tree

2) Auxillary Space:- O(h)….

 bcoz of extra space of the call stack
 h = height of the Binary Tree

3) Interesting fact :-
 Inverting a Binary Tree  Converting a BT to it’s mirror image.

https://www.techiedelight.com/delete-given-binary-tree-iterative-recursive/
Q) Deleting a Binary Tree (Iterative and Recursive).

Recursive Soln.

1) Traverse the BT in a postorder fashion.

 Then delete the left and right subtree of a node.
 Before deleting the node itself.

2) Note :-
 We cannot traverse the BT in a inorder or preorder fashion.
 Bcoz we cannot delete a parent before deleting it’s children.

Ex1) Code (Recursive Soln)

void deleteBinaryTree1(Node* &root)
{
    // Base Case (Empty Tree)
    if(root == nullptr)
        return;

    // Delete left,right subtree first (Postorder traversal)
    deleteBinaryTree1(root->left);
    deleteBinaryTree1(root->right);

    // Delete the current node after deleting its left and right subtree
    delete root;

    // Set root to null before returning.
    root = nullptr;
}

Iterative Soln.

1) In the iterative soln

 We perform a level order traversal on the BT.

2) Delete each node in the queue q one by one

 after pushing their non-empty left and right child to the queue q.

3) It is important to delete the front node ONLY after enqueuing its children

4) Set root as null before returning

Ex2) Code (Iterative Soln)

void deleteBinaryTree2(Node* &root)
{
    if(root == nullptr)
        return;

    queue<Node*> q;
    q.push(root);

    Node* x = nullptr;

    while(!q.empty())
    {
        // Delete each node in the queue q one by one after pushing their
        // non-empty left and right child to the queue q.
        x = q.front();
        q.pop();

        if(x->left != nullptr)
            q.push(x->left);
        
        if(x->right != nullptr)
            q.push(x->right);

        // It is important to delete the front node ONLY after enqueuing its children
        delete x;
    }
    // set root as null before returning
    root = nullptr;

Q) LCA of 2 nodes in a BT

1) Suppose T = Rooted BT
 n1 , n2 = Any 2 nodes in the BT.

2) LCA(n1, n2) = Lowest Common Ancestor of n1, n2.

 It is the common shared ancestor of n1,n2 such that it is farthest from the root.

3) For eg.
 Ancestors of (6,12) = 10,15
 LCA(6, 12) = 15.
 Bcoz among 10, 15  15 is farthest from the root of the Tree.

https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
Ex1) Solution 1

1) Store the nodes on the path from root to n1

 in a Auxillary array path1.

2) Store the nodes on the path from root to n2

 in a Auxillary array path2.
3) Then traverse both pathays path1, path2 simultaneously and stop when a mismatch is found.
 The last matched value is the LCA(n1, n2).
 Last matched value = That matched value just after which the mismatch occurs.

4) While traversing path1, path2 simultaneously

 Suppose end of path1 is reached  Then the last value of path1 is the LCA.
 Suppose end of path2 is reached  Then the last value of path2 is the LCA.

https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

Q) LCA(n1, n2) in BST

1) Calculating LCA for BST is even more easy than the previous one.

2) If (value of curr Node) > (n1 && n2)

 Then LCA(n1, n2) lies in the left subtree of (curr Node).

3) If (value of curr Node) < (n1 && n2)

 Then LCA(n1, n2) lies in the right subtree of (curr Node).

4) If the above 2 cases are false

 Then the current Node (i.e curr) is the LCA.

5) The above procedure assumes that the Nodes n1, n2 are already present in the BST.
Ex1) Recursive Implementation of the Above Logic.
Ex2) Iterative implementation of the above logic.

https://www.geeksforgeeks.org/minimum-swap-required-convert-binary-tree-binary-search-tree/

Q) Count number of swaps needed to convert BT to BST.

1) Inorder traversal of the above BT = arr = {8, 6, 9, 5, 10, 7, 11}

 arr = {8, 6, 9, 5, 10, 7, 11}
 sorted_arr = {5, 6, 7, 8, 9 , 10, 11}
 No. of swaps needed to convert arr to sorted_arr = 3.
 No. of swaps required to convert an array to it’s sorted array is already discussed in the So

2) Now Inorder traversal of BST = sorted_arr = {5, 6, 7, 8, 9 , 10, 11}

 Create a BST from the above inorder traversal.

3) So number of swaps needed to convert BT to BST = number of swaps needed to convert arr to
 arr = Inorder traversal of BT.
 sorted_arr = Inorder traversal of BST.

4)

Q) Various Tree Traversals

Q) Introduction

1) Unlike linked lists, 1D arrays, and other linear data structures , which are traversed in linear o
 Trees can be traversed in multiple ways in  depth–first order  (preorder , inorder , and postor
 or breadth–first order  (level order traversal ).
2) Beyond these basic traversals,
 various more complex or hybrid schemes are possible,
 such as depth-limited searches like iterative deepening depth–first search.

3) Traversing a tree involves iterating over all nodes in some manner.

 As the tree is not a linear data structure,
 There can be more than one possible next node from a given node,
 so some nodes must be deferred, i.e., stored in some way for later visiting.

4) The traversal can be done iteratively where the deferred nodes are stored in the  stack ,
 or it can be done by  recursion , where the deferred nodes are stored implicitly in the  call st

Ex1) The Program

 Recursive Preorder Traversal
 Recursive Inorder Traversal.
 Recursive Postorder Traversal.

// Recursive InOrder Traversal 😎😎 // Recursive PreOrder Travers
void inorder1(Node* root) void preorder1(Node* root)
{ {
    if(root == nullptr)     if(root == nullptr)
        return;         return;

    inorder1(root->left);     cout<<root->data<<",";
    cout<<root->data<<",";     preorder1(root->left);   
     inorder1(root->right);     preorder1(root->right);
    
} }

Output :- Output :-
Inorder Traversal :- 4,2,1,7,5,8,3,6, Preorder Traversal :- 1,2,4,3,

// Recursive PostOrder Traver
void postorder1(Node* root)
{
    if(root == nullptr)
        return;

    postorder1(root->left);  
    postorder1(root->right);
    cout<<root->data<<",";
    
}

Output :-
Postorder Traversal :- 4,2,7,8

Ex2) Time Complexities

1) Time Complexity = O(n)

 n  No. of nodes in the Tree.

Q) Basic Problems on Level Order Traversals in a BT.

Q) Level Order Traversal (Using Queue)
 Answer = 1,2,3,4,5,6,7

1) Declare a empty queue q

2) Push the root node into the queue

3) While queue q is not empty

 Dequeue a node(say x) from the queue
 and then print it's data….
 i.e now node x is visted
 If x's left child is not NULL….
 i.e if xleft is not NULL…
 then enqueue x.left into the queue q
 If x's right child is not NULL….
 i.e if xright is not NULL…
 then enqueue x.right into the queue q

Ex1) Code
// Function to print level order traversal of a given binary tree
void print_level_order(Node* root)
{
    if(root == NULL)
        return;

    // create an empty queue and enqueue the root node
    queue<Node*> q;
    q.push(root);

    // Loop till the Queue is empty.
    while(!q.empty())
    {
        Node* x = q.front();
        cout<<x->data<<",";
        q.pop();

        if(x->left != NULL){
            q.push(x->left);
        }

        if(x->right != NULL){
            q.push(x->right);
        }
    }
}

1) Time Complexity :- O(n)

 n = number of nodes in the binary tree

2) Auxillary Space:- O(n)

 i.e a queue is used
Q) Level Order Traversal (Recursively)
 Answer = 1,2,3,4,5,6,7

Ex1) Code

// Find ht of the given Node x. // Print the nodes at the sp
int height(Node* x) // From Left to Right (Defaul
{ void print_given_level(Node* 
    if(x == NULL) {
        return 0;     if(root == NULL)
        return;
    int lheight = height(x->left);
    int rheight = height(x->right);     if(level == 1)
        cout<<root->data<<","
    return max(lheight+1,rheight+1);
}     print_given_level(root->l
    print_given_level(root->r
}

void print_level_order(Node* 
{
    int h = height(root);
    int i;

    for(i=1;i<=h;i++)
    {
        print_given_level(roo
    }
}
Q) Spiral Level Order Traversal (Recursively)
 Answer = 1, 2,3 7,6,5,4

Ex1) Code

1) Everything same as before (Except this difference)

void print_spiral_order(Node* root)
{
    int h = height(root);
    int i;

    for(i=1;i<=h;i++)
    {
        if(i%2)
            print_level_right_to_left(root,i);
        else
            print_level_left_to_right(root,i);
    }
}

1) Concept :-
 At the Odd Level  print nodes from right to left
 At the Even Level  print nodes from left to right

Q) Invert a Binary Tree

https://www.techiedelight.com/invert-binary-tree-recursive-iterative/

Q) Invert a Binary Tree (Traversing Recursively in pre-order/postorder fashion)

re

Step 1 (Recursive) :-
1) Traverse the given tree in pre-order/post-order fashion

2) For each Node x encountered…..

 Swap the left,right child of Node x

3) Then recursively invert the Left and Right Subtree of Node x as well

Ex1) Illustration 1
// Inverting the Binary Tree by traversing the tree in a pre-order fashion
void invertBinaryTree1(Node* root)
{
    if(root == nullptr)
        return;

    // Swap the left and right child of the current Node 
    swap(root->left,root->right);

    // Invert Left Subtree of current Node
    invertBinaryTree1(root->left);

    // Invert Binary Tree of current Node
    invertBinaryTree1(root->right);
}

Ex2) Illustration 2
// Inverting the Binary Tree by traversing the tree in a post-order fashion
void invertBinaryTree2(Node* root)
{
    if(root==nullptr)
        return;

    // Invert Left Subtree of current Node
    invertBinaryTree2(root->left);
    // Invert Binary Tree of current Node
    invertBinaryTree2(root->right);

    // Swap the left and right child of the current Node 
    // Swap mtlb mutlaq swap...and not merely swapping their data
    swap(root->left,root->right);
}

Ex3) Illustration 3
// Inverting the Binary Tree by traversing the tree in a pre-order fashion
Node* invertBinaryTree1(Node* root)
{
    if(root==nullptr)
        return root;

    // Swap the left and right child of the current Node 
    // Swap mtlb mutlaq swap...and not merely swapping their data
    swap(root->left,root->right);

    // Invert Left Subtree of current Node
    invertBinaryTree1(root->left);

    // Invert Binary Tree of current Node
    invertBinaryTree1(root->right);

return root;
}

1) Time Complexity:- O(n)

 n = Number of nodes in the binary tree

2) Auxillary Space:- O(h)….

 bcoz of extra space of the call stack
 h = height of the Binary Tree

3) Interesting fact :-
 Inverting a Binary Tree  Converting a BT to it’s mirror image.

Q) Printing Top, Bottom, Right, Left Views of a BT

https://www.techiedelight.com/print-left-view-of-binary-tree/
Q) Print Left View of the BT
 Left View of BT = 1, 2, 4, 7

1) We will modify the Level Order Traversal a little bit.

2) For each level of the BT.

 Print the first node of that level.

Ex1) Code
// Iterative function to print the left view of a given binary tree
void leftView(Node* root)
{
    // return if the tree is empty
    if (root == nullptr) {
        return;
    }
 
    // create an empty queue and enqueue the root node
    queue<Node*> q;
    q.push(root);
 
    // pointer to store the current node
    Node* curr = nullptr;
 
    // loop till queue is empty
    while (!q.empty())
    {
        // calculate the total number of nodes at the current level
        int size = q.size();
        int i = 0;
 
        // process every node of the current level 
        // and enqueue their non-empty left, right child
        while (i++ < size)
        {
            curr = q.front();
            q.pop();
 
            // if this is the first node of the current level, print it
            if (i == 1) {
                cout << curr->data << ",";
            }
 
            if (curr->left) {
                q.push(curr->left);
            }
 
            if (curr->right) {
                q.push(curr->right);
            }
        }
    }
}

https://www.techiedelight.com/print-bottom-view-of-binary-tree/
Q) Print Bottom View of a BT.
 Bottom View = 7, 5, 8, 6.
 (horizontal distance —> (node’s valu

-1 —> (7, 4)
0 —> (5, 3)
1 —> (8, 4)
2 —> (6, 3)

1) Think Like
 x coord  horiz_dis
 y coord  (node_value, node_level) O
 y coord  (node_level, node_value)
 x coord  key , y coord  value

1) We can solve this problem using Hashing :-

2) Create a empty map(unordered_map)

 key  Horizontal Distance of the node)
 value  Pair(Curr node’s value, Curr node’s level).
 Horizontal Node  Calculated from the root node.

3) Perform a pre-order traversal (DFS) on the tree.

 If the (current level of node) >= (maximum level seen so far) for the same horizontal dista
 Or if the horizontal distance corres to the current level is seen for the first time,
 Then update the (Curr node’s value, Curr node’s level).
 Bcoz in bottom , For the same horiz dis , We consider the bottommost (i.e max) level.

Ex1) The Program

// Priniting the contents of the Map prints the Bottom View of the bt
void generateBottomView(Node* node, int dist, int level, map<int, pair<int, int>> &m)
{
    // base case: empty tree
    if (node == nullptr) {
        return;
    }
 
    // If the (current level of node) >= (maximum level seen so far) for the same horizontal 
    // Or if the horizontal distance is seen for the first time, update the map
    // Then update the (Curr Node's value, Curr Node's value).
    // Bcoz for same hoiz dis , level must be the bottommost(max)
    if (  (level >= m[dist].second) || (m.find(dist) == m.end())   )
    {
        // update value and level for the current distance
        m[dist] = { node->data, level };
    }
 
    // Recur for the left subtree
    // Hence level = level + 1
    // Horizontal dist = dist = dist - 1
    generateBottomView(node->left, dist - 1, level + 1, m);
 
    // Recur for the Right subtree
    // Hence level = level + 1
    // Horizontal dist = dist = dist + 1
    generateBottomView(node->right, dist + 1, level + 1, m);
}

// Function to print the bottom view of a given binary tree
void printBottomView(Node* root)
{ 
    map<int, pair<int, int>> m;
 
    // perform preorder traversal on the tree and fill the map
    generateBottomView(root, 0, 0, m);
 
    // traverse the map and print the bottom view
    for (auto it: m) {
        cout << it.second.first << " ";
    }
}

Q) Some Basic Problems on Binary Tree

Q) Finding Height of a Node x in a Binary Tree

Ex1) Finding Height of a Node ‘node’ in a BT

 Height of Node ‘node’ = No. of edges in the path from ‘node’ to deepest leaf + 1
 Height of Node ‘node’ = No. of nodes in the path from ‘node’ to deepest leaf
 Ht(8) = 3 + 1 = 4
 Ht(4) = 2 + 1 = 3
 Write the appropriate code

1) Approach :-
 Ht of root = 1 + max(Ht. of left subtree,Ht. of right subtree).
 Plus 1 = To include the root also

int height1(Node* node)
{
    if(node == NULL)
        return 0;
    
    int lheight = height1(node->left);
    int rheight = height1(node->right);
    
    return 1 + max(lheight,rheight);
}

Ex2) Finding Height of a Node node in a BT

 Height of Node ‘node’ = No. of edges in the path from ‘node’ to deepest leaf
 Ht(8) = 3 = 4
 Ht(4) = 2 = 3
 Write the appropriate code

1) Approach :-
 Ht of root = 1 + max(Ht. of left subtree,Ht. of right subtree).
 Plus 1 = To include the root also

int height1(Node* node)
{
    if(node == NULL)
        return -1;
    
    int lheight = height1(node->left);
    int rheight = height1(node->right);
    
    return 1 + max(lheight,rheight);
}

2) Time Complexity :-
 Time Complexity = O(n).
 Since we are going to each and every node of the BT.
 n = No. of nodes in the BT.

Ex2) Finding Height of a Node node in a BT

int height(Node* node)
{
    int lheight = 0;
    int rheight = 0;
    
    if (node->left != nullptr)
        lheight = 1 + height(node->left);

    if (node->right != nullptr)
        rheight = 1 + height(node->right);

    // return max(lheight,rheight);
    return lheight > rheight ? lheight:rheight;
}
Q) Find the Diameter(width) of a BT

1) Diameter of a tree is also known as the width of the Tree

2) Diamter of a Tree
 No. of nodes on the longest path containing two leaf nodes.

3) Example 1:-
 (4 to 7)  (4  2  1  3  5  7)  No. of Nodes = 6
 (4 to 8)  (4  2  1  3  5  8)  No. of Nodes = 6
 (4 to 6)  (4  2  1  3  6)  No. of Nodes = 5
 (7 to 8)  (7  5  8)  No. of nodes = 3
 (7 to 6)  (7  5  3  6)  No. of nodes = 4
 (8 to 6)  (8  5  3  6)  No. of nodes = 4

4) Hence in example 1
 Diameter of tree = No. of nodes from (4 to 7) = No. of nodes from (4 to 8) = 6.

Ex1) Write a function to compute the diameter of this tree

int height1(Node* node)
{
    if(node == NULL)
        return -1;
    
    int lheight = height1(node->left);
    int rheight = height1(node->right);
    
    return 1 + max(lheight,rheight);
}

int diameter1(Node* node)
{
    if(node == NULL)
        return 0;

    int ld = diameter1(node->left);
    int rd = diameter1(node->right);
    int sp = height1(node->left) + height1(node->right) + 2;

    return max(max(ld,rd),sp);// Return max(ld,rd,sp) basically
}
Concept:-
 ld = Diamter of the left subtree
 rd = Diamter of the right subtree

Time Complexity
 Time Complexity = O(n 2 )
 There are n nodes in the tree.
 For each node … We are calling the height1() function [height1() takes O(n) time ]
 Hence we are getting O(n 2 ) time complexity.
 See vid. At 38:40

Ex2) Reducing the Time Complexity to O(n).

 Q) Binary Tree Basic operations
Q) BST Basic Operations and properties
Q1) What is a BST

Binary Search Tree is a special kind of Binary Tree wherein

 Left subtree of any node x contains nodes with value
lesser than the Node x’s value
 Right subtree of any node x contains nodes with value
greater than the Node x’s value
 The left and right subtree of the Node x must also be a BST
 There must not be any duplicate nodes  Each node of BST should be unique
 Hence by definition. BST must contain unique keys only

Q2) What do you mean by Skewed BST’s

1) A Binary Tree which is dominated by mostly left or right children is known as

Skewed Binary Trees

2) Left Skewed Binary Tree

 most of the Nodes have left child without corresponding right child
 Partially Left dominated Tree

3) Right Skewed Binary Tree =

 most of the Nodes have left child without corresponding right child
 Partially Right dominated Tree

4) If the Left Skewed,Right Skewed BT’s are BST’s

 Then they are called Left/Right Skewed BST’s
5) In the figure shown……They are completely left skewed/right skewed BST’s

6) Completely Left Skewed BT

 All Nodes have a Left child or no child
 No node has a right child
 All Right children remain null
 Completely Left Dominated Tree

7) Completely Right Skewed BT

 All Nodes have a right child or no child
 No node has a left child
 All Left children remain null
 Completely Right Dominated Tree

Q1) Search the following keys in the BST Q2)

 45
 22

1) Let’s Search 45
 45 > 25  Go to right of 25  50 encountered
 45 < 50  Go to the left of 50  35 encountered
 45 > 35  Go to the right of 35  44 encountered
 45 > 44  Go to the right of 44  NULL encountered
 Hence 45 is not present in the BST

2) Let’s search 22
 22 < 25  Go to the left of 25  15 encountered
 22 > 15  Go to the right of 15  22 encountered
 Hence we have got 22  It is present to the left of 15
 Q)
1) T

2) I
cont
i

3) I
valu

4) S
N

Ill1
// F
// I
Node
{
    
    
    
    
    
    
}

Q) Find the minimum element(key) from a BST(recursively) https

%20
1) To find minimum key in the BST……
 Start from the root Q) I
 Keep on following the left children of each Node
starting from the root till NULL is encountered // R
Node
2) If the root doesn’t have a left child(i.e no left subtree)…… {
 Then the key contained in the root is the smallest element     
    
3) In simple words the     
 left-most leaf node of a BST contains the key with minimum value     
    
4) Since subtrees of a BST is also a BST……
 Hence using this approach we can find the Node with minimum key     
 starting from any Subtree rooted at x     
    
Ill1) Illustration 1(Iterative Method)     
// Finding  the Minimum  Value  Node  from  the subtree  rooted  at x     
// If x = root  node...     
// Then  this  method  finds  the min  value  in the  entire BST
Node * find_min1 (Node * &x)     
{     
    Node * curr  = x;     
    
    while (curr ->left  != NULL )     
    {     
        curr  = curr ->left ;     
    } }

    return  curr ; 1) T
} 




Q) Time Complexity of BST Operations :-

1) Basic BST operations include :-

 Insertion of a key x
 Deletion of a key x
 Accessing a key x.
 Searching key x
 Finding min,max element of BST (like this).
 These operations visit the nodes along a (root  leaf ) path basically

2) All BST operations have the following time complexity :-

 Average Time = θ(h) = θ(log 2 n)
 Worst Time = O(n)
 h = log 2 n = Ht. of the BST
 n= No. of nodes of the BST.

3) Average Case :-
 Occurs for Ht. Balanced BST’s (AVL,RB,and normal balanced BST’s).

4) Worst Case :-
 Occurrs for Skewed BST’s .
 Bcoz for Skewed BST’s Ht becomes n (h = n).
 Hence Time Complexity becomes O(n).
 Also BST’s are not guaranteed to be self balanced (Considering the properties of
BST).
5) BST in Worst Case (i.e Skewed BST’s) :-
 Has O(n) Time complexity of operations
 Hence are no more efficient than a regular linked list.
 Hence works like an linear unordered array/list.

6) Hence to improve average time performance of various BST operations

 AVL Trees,Red-Black Trees
 And other Self Balancing BST’s are actually brought forth in the icture.

Q) AVL Tree Basics

Q) What are AVL Trees ?? Q

1)
1) AVL Trees are a special Kind of BST’s
2)
2) AVL Tree is a BST wherein
 ht. of left_subtree and right_subtree of every node differs by atmost one
 They are a special kind of BST wherein b.f of every node = {-1,0,1}

4) They are also called self-balancing BST’s 3)

4)

5) b.f of a node x = Balance Factor of that node x

= Ht.(left subtree of Node x) – Ht.(Right subtree of Node x) 5)
 In AVL Tree b.f of any node = {-1,0,1}
 Obviously in any tree………b.f(leaf nodes) = 0 Ex

Ex1) Concept 😊 😊 1)

Q) Threaded Binary Trees

1) In-Order Traversal of a BT is done by either recursion or by using a stack

2) The main idea of threaded BT

 is to make In-order traversal faster and do it without stack and without recursion.
3) There are 2 types of threaded BT's
 Single Threaded Binary Tree
 Double Threaded Binary Tree

4) Single Threaded Binary Tree (Right Threaded Binary Tree)

 Where NULL right pointers are made to point to the in-order successor (if exists)
 (if successor exists)

5) Single Threaded Binary Tree (Left Threaded Binary Tree)

 Where NULL left pointers are made to point to the in-order predecessor (if exists)
 (if predecessor exists)

4) Double Threaded Binary Tree

 Where NULL right pointers are made to point to the in-order successor(if exists)
 and NULL left pointers are made to point to the in-order predecessor(if exists)
 The predecessor threads are usefull for in-order and post-order traversal.
 Double Threaded BT is called 2-way threaded BT
 2-way Threaded BT is called Fully Threaded BT.

Ex1) Advantages of Threaded BT’s

1) It enables linear traversal of elements in the tree.

 Linear Traversal eliminates the use of stacks for inorder traversal.
 In turn a lot of memory space is needed and consumed.

2)