Trees and Binary Search Trees

1

if treeRoot1 and 2 both NULL -> return true

if both not NULL -> compare

return (treeRoot1->data == treeRoot2->data

&& recursive to treeRoot1's left and treeRoot2's left

&& recursive to treeRoot1's right and treeRoot2's right)

// else, if one is empty and one is not, not identical

return false

ideas

- BST in in0order(left->root0>right) & store in array

- get kth from array

if curr == NULL, return

create new queue

enqueue the current node

start while loop (until queue is empty != 1

head = dequeue from the new queue

print the head

if head->left is not null, recursive to head left

if head->right is not null, recursive to head right

end while loop

free queue

if curr == NULL, return 0

if curr->left == NULL & curr->right == NULL

-> return 1+left recursive + right recursive

// if curr node is not lead node (has child node), keep search

return 0 + left recursive + right recursive

if curr == NULL return new node

else if value < curr->value

curr->left = recursive to left

else if value > curr->value

curr->right = recursive to right

// if same value, don't insert the duplicate
return curr

if curr == NULL, return false

else if value < curr->value -> recursive to left

else if value > curr->value -> recursive to right

else (value == curr->value) return true

in BST

• size 3 ⇒ 2 search
• size 7 ⇒ 3 search
• size 15 ⇒ 4 search
• size 100 ⇒ 7 search
• size 10,000 ⇒ 13 search
• size 1,000,000 ⇒ 20 search….
• size n ⇒ log 2 n search
• size times 2 ⇒ search + 1
• 

bstNumLeaves: (takes in node *t)

if t is NULL, return 0

else if t->left and t->right are NULL (leaf)

return 1;
else: return recurse(left) + recurse(right)

bstRange: (diff between smallest and largest values) (takes in node *t)

if t is NULL, return -1

create a pointer to current min value, current max value

set these to t.

while loop currl minnot NULL, curr->left

while loop curr max not null, currmax->right

return currmax - curmin

bstDeleteLeaves (takes in node *t)

if t is NULL, return NULL

else if t->left and t->right are NULL we delete:
free(t)
return NULL;

else {

point t->left to recursed(left)
point t->right to recursed(Right)

bstLevelOrder (takes in node *t) Level-Order Traversal of a BST

type void

if t is NULL, return

make a new queue
enqueue node t onto t.

while loop: whiile the queue is not empty

point to a newnode *n = Dequeue(q)

printndoe(n)

if n-> left is NULL, then enqueue n left
if n right is NULL, then enqueue n right

after while loop free q.

int cmp1 = compare string between two names

return cmp1 if cmp1 is not NULL

int cmp2 = compare string between two names

return cmp2 if cmp2 is not NULL

if name is all null, return zid difference

return zid of student 1 - zid of student 2

current node = given root node

start while loop where curr is not NULL

if given value < curr value

curr = curr's left

else if given value > curr value

curr = curr's right

else (when given value is found) return the curr node

return curr node (when given value is not in the tree)

if node is NULL, return false

answer = false

the leftover sum will be target(given) sum - current node's value

if leftover is 0 and also the current node is leaf node, return true

if roof's left is not NULL, answer will be answer || recursive for root's left

and same for the right

if node is NULL, return true

if root's left is not NULL AND root value is smaller or equal than root's left value, then it's false

else if for right, return is false as well

bool answer = false;

answer = answer OR recursive for right

answer = answer OR recursive for left

return the answer bool value

if node is NULL return 0

return 1 + recursive left + recursive right

<find if it's identical>

if root and subtree's root are NULL, return true

if root or subtree's root are NULL, return false

return root's value == subroot's value AND recursive with root&subroot left AND recursive with root&subroot right

<subtree find>

if subtree's root is NULL, return true

if root is NULL, return false

find identical and if true, return true

return subtree finding recursion with root left OR subtree finding recursion with root right

integer numberofnode = get total number of node in tree from other function

array of integer to sort

set index to pass through parameter to get pre-order tree

do pre-order

find minimum diff from sorted array list

-> set min abs(array[0]-array[1]) like normal munimum finding in array

return minimum difference

void dopreorder

tree recursive function

if root is NULL, return

if not, add root value to sort array

find preorder left

find preorder right

traverse through left until current node is NULL

< do main >

if the root is NULL, return

if root value is greater of equal with the range and smaller or equal with range

add the root value to the pointer sum

recursive call to root->left

recursive call to root->right

< call >

set int sum

call do main part with &sum

return the sum

<do main>

if root is NULL return

if root's left is not NULL && root's left's left is not NULL and root's right's right is not NULL

pointer of sum is increased by root's left value

recursive of root's left

recursive of root's right

<call here>

pass the int sum = 0 address to the main function

do main function

and return sum

// Define the structure for a tree node 
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};
// Function to create a new tree node 
struct TreeNode* createNode(int item) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = item;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// Function to insert a node into the tree 
struct TreeNode* insert(struct TreeNode* root, int item) {
    if (root == NULL) {
        return createNode(item);
    }
    if (item < root->data) {
        root->left = insert(root->left, item);
    } else if (item > root->data) {
        root->right = insert(root->right, item);
    }
    return root;
}
// Function to find the minimum node in the tree 
struct TreeNode* findMin(struct TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}
// Function to delete a node from the tree 
struct TreeNode* delete(struct TreeNode* root, int item) {
    if (root == NULL) {
        return root;
    }
    if (item < root->data) {
        root->left = delete(root->left, item);
    } else if (item > root->data) {
        root->right = delete(root->right, item);
    } else {
        // Node with only one child or no child
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // Node with two children: get the inorder successor (smallest in the right subtree)
        struct TreeNode* temp = findMin(root->right);
        // Copy the inorder successor's content to this node
        root->data = temp->data;
        // Delete the inorder successor
        root->right = delete(root->right, temp->data);
    }
    return root;
}
// Function to search for a node in the tree 
struct TreeNode* search(struct TreeNode* root, int item) {
    if (root == NULL || root->data == item) {
        return root;
    }
    if (item < root->data) {
        return search(root->left, item);
    }
    return search(root->right, item);
}

Level Order Traversal(BST t):

initialise an empty queue

add t's root node to the queue

while the queue is not empty

do remove the node at the front of the queue

print the value in the node

add its left child (if any) to the queue

add its right child (if any) to the queue

end while

// Function to perform level order
// traversal on the Tree and
// calculate the required sum
int rangeSumBST(Node* root, int low,
                int high)
{
    // Base Case
    if (root == NULL)
        return 0;
    // Stores the nodes while
    // performing level order traversal
    queue<Node*> q;
    // Push the root node
    // into the queue
    q.push(root);
    // Iterate until queue is empty
    while (q.empty() == false) {
        // Stores the front
        // node of the queue
        Node* curr = q.front();
        q.pop();
        // If the value of the node
        // lies in the given range
        if (curr->val >= low
            && curr->val <= high) {
            // Add it to sum
            sum += curr->val;
        }
        // If the left child is
        // not NULL and exceeds low
        if (curr->left != NULL
            && curr->val > low)
            // Insert into queue
            q.push(curr->left);
        // If the right child is not
        // NULL and exceeds low
        if (curr->right != NULL
            && curr->val < high)
            // Insert into queue
            q.push(curr->right);
    }
    // Return the resultant sum
    return sum;
}

// A recursive function to construct BST from post[].
// postIndex is used to keep track of index in post[].
struct node* constructTreeUtil(int post[], int* postIndex,
                         int key, int min, int max, int size)
{
    // Base case
    if (*postIndex < 0)
        return NULL;
    struct node* root = NULL;
    // If current element of post[] is in range, then
    // only it is part of current subtree
    if (key > min && key < max)
    {
        // Allocate memory for root of this subtree and decrement
        // *postIndex
        root = newNode(key);
        *postIndex = *postIndex - 1;
        if (*postIndex >= 0)
        {
          // All nodes which are in range {key..max} will go in right
          // subtree, and first such node will be root of right subtree.
          root->right = constructTreeUtil(post, postIndex, post[*postIndex],
                                          key, max, size );
          // Construct the subtree under root
          // All nodes which are in range {min .. key} will go in left
          // subtree, and first such node will be root of left subtree.
          root->left = constructTreeUtil(post, postIndex, post[*postIndex],
                                         min, key, size );
        }
    }
    return root;
}
// The main function to construct BST from given postorder
// traversal. This function mainly uses constructTreeUtil()
struct node *constructTree (int post[], int size)
{
    int postIndex = size-1;
    return constructTreeUtil(post, &postIndex, post[postIndex],
                             INT_MIN, INT_MAX, size);
}

// Check if the given Binary Tree is Symmteric
bool isMirror(Node* root1, Node* root2)
{
    // If both trees are empty, then they are mirror images
    if (root1 == NULL && root2 == NULL)
        return true;
    // For two trees to be mirror images, the following
    // three conditions must be true
    // 1.) Their root node's key must be same
    // 2.) left subtree of left tree and right subtree of
    // right tree have to be mirror images
    // 3.) right subtree of left tree and left subtree of
    // right tree have to be mirror images
    if (root1 && root2 && root1->key == root2->key)
        return isMirror(root1->left, root2->right)
               && isMirror(root1->right, root2->left);
    // if none of above conditions is true then root1
    // and root2 are not mirror images
    return false;
}
// Returns true if a tree is symmetric i.e. mirror image of
// itself
bool isSymmetric(Node* root)
{
    // Check if tree is mirror of itself
    return isMirror(root, root);
}

// Code to mirror a tree 
void mirror(struct Node* node)
{
    if (node == NULL)
        return;
    else {
        struct Node* temp;
        /* do the subtrees */
        mirror(node->left);
        mirror(node->right);
        /* swap the pointers in this node */
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}

// Find the number of reachable vertices from a given src
static int doNumReachable(Graph g, int v, int visited[])
{
    visited[v] = true;
    int numR = 1;
    for (int w = 0; w < GraphNumVertices(g); w++)
    {
        if (GraphIsAdjacent(Graph g, Vertex v, Vertex w) && visited[w] == false)
        {
            numR = numR + doNumReachable(g, w, visited);
        }
    }
    return numR;
}
int numReachable(Graph g, int src) {
    bool *visited = malloc(GraphNumVertices(g) * sizeof(bool *));
    int numR = doNumReachable(g, v, visited);
    free(visited);
    return numR;
}

// Tree is perfeclty balanced
bool TreeIsPerfectlyBalanced(Tree t) {
    if (t == NULL) {
        return true;
    }
    int l = BSTreeSize(t->left);
    int r = BSTreeSize(t->right);
    if (l - r > 1 || r - l > 1) {
        return false;
    } else {
        return TreeIsPerfectlyBalanced(t->left) &&
               TreeIsPerfectlyBalanced(t->right);
    }
}

// BST Tree Size
static int BSTreeSize(BSTree t) {
    if (t == NULL) {
        return 0;
    } else {
        return 1 + BSTreeSize(t->left) + BSTreeSize(t->right);
    }
}

// Get the Kth Element of the Binary Tree (Accessending order)
int BSTreeGetKth(BSTree t, int k) {
    int leftSize = BSTreeSize(t->left);
    if (k == leftSize) {
        return t->value;
    } else if (k < leftSize) {
        return BSTreeGetKth(t->left, k);
    } else {
        return BSTreeGetKth(t->right, k - leftSize - 1);
    }
}

// Sum of all odd nodes in a Binary Tree
int TreeSumOdds(Tree t) {
    if (t == NULL)
    {
        return 0;
    }
    else 
    {
        int add = 0;
        if (t->value % 2 == 1)
        {
            add = t->value;
        }
        return add + TreeSumOdds(t->left) + TreeSumOdds(t->right);
    }
    return 0;
}

// Find the depth of a node in the BST
int BSTreeNodeDepth(BSTree t, int key) {
    if (t == NULL) {
        return -1;
    } else if (key == t->value) {
        return 0;
    } else if (key < t->value) {
        int depth = BSTreeNodeDepth(t->left, key);
        return (depth == -1 ? -1 : depth + 1);
    } else {
        int depth = BSTreeNodeDepth(t->right, key);
        return (depth == -1 ? -1 : depth + 1);
    }
}

// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil(int pre[], int preIndex, int low, int high, int size)
{
    // Base case
    if (preIndex >= size || low > high)
        return NULL;
    // The first node in preorder traversal is root. So take
    // the node at preIndex from pre[] and make it root, and
    // increment preIndex
    struct node* root = newNode(pre[*preIndex]);
    preIndex = preIndex + 1;
    // If the current subarray has only one element, no need
    // to recur
    if (low == high)
        return root;
    // Search for the first element greater than root
    int i;
    for (i = low; i <= high; ++i)
        if (pre[i] > root->data)
            break;
    // Use the index of element found in preorder to divide
    // preorder array in two parts. Left subtree and right
    // subtree
    root->left = constructTreeUtil(pre, preIndex, preIndex, i - 1, size);
    root->right = constructTreeUtil(pre, preIndex, i, high, size);
    return root;
}
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree(int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil(pre, preIndex, 0, size - 1, size);
}

// Find the height of a BSTree 
int TreeHeight(Tree t) {
    if (t == NULL)
    {
        return -1;
    }
    int leftHeight = TreeHeight(t->left);
    int rightHeight = TreeHeight(t->right);
    if (leftHeight > rightHeight)
    {
        return leftHeight + 1;
    }
    else 
    {
        return rightHeight + 1; 
    }
    return -1;
}

// insert a new value as root of Tree

 Tree insertAtRoot(Tree t, Item it) { 
    if (t == NULL) 
        return newNode(it); 
    int diff = cmp(key(it), key(t->value)); 
    
    if (diff == 0) 
        t->value = it; 
    else if (diff < 0) { 
        t->left = insertAtRoot(t->left, it); 
        printf("rotateR(%d)\n",t->value); 
        t = rotateR(t); 
    } else if (diff > 0) { 
        t->right = insertAtRoot(t->right, it); 
        printf("rotateL(%d)\n",t->value); 
        t = rotateL(t); 
    } 
    return t; 
}

int count(Tree t) {
return t == NULL ? 0 : 1 + count(t -> left) + count(t -> right);

}

Tree Partition(Tree t, int newRootIndex) {
int leftNumNodes = countNodes(t -> left);

if (leftNumNodes > newRootIndex) { // The rootIndex is somewhere in the left subtree

t -> left = Partition(t -> left, newRootIndex);

t = rotateRight(t); // Rotate right, to lift the new median node up to root

}

bool BSTSearch(BSTree t, int target) {

if (t == NULL) return false;

subtree

if (t -> value == target) { // Target has been reached

return true;

}
else if (target < t -> value) { // Go search for the target in the left subtree

return BSTSearch(t -> left, target);

}
else if (target > t -> value) { // Go search for the target in the right subtree

return BSTSearch(t -> right, target);

}

}

Preorder

root->left->right

void preorder(BST t) {

if(t=NULL) return;

printf("%d ", t->value);

preorder(t->left);

preorder(t->right);

}

Inorder

left->root->right

void inorder(BST t) {

if(t=NULL) return;

inorder(t->left);

printf("%d ", t->value);

inorder(t->right);

}

postorder

left->right->root

void postorder(BST t){

if(t=NULL) return;

postorder(t->left);

postorder(t->right);

printf("%d ", t->value);

}

static int *findPathBfs(Graph g, Vertex src, Vertex dest, int max) {

int *pred = calloc(g->nV, sizeof(int));

assert(pred != NULL);

for (Vertex v = 0; v < g->nV; v++) {

pred[v] = -1;

}

pred[src] = src;

Queue q = QueueNew();

QueueEnqueue(q, src);

bool found = false;

while (!found && !QueueIsEmpty(q)) {

Vertex v = QueueDequeue(q);

for (Vertex w = 0; w < g->nV; w++) {

if (g->edges[v][w] <= max && pred[w] == -1) {

pred[w] = v;

if (w == dest) {

found = true;

break;

}

QueueEnqueue(q, w);

}

}

}

QueueFree(q);

return pred;

}

// find bfs from source

int findPath(Graph g, Vertex src, Vertex dest, int max, int *path) {

assert(g != NULL);

int *pred = findPathBfs(g, src, dest, max);

if (pred[dest] == -1) {

free(pred);

return 0;

}

// fill path array in reverse

int pathLength = 0;

Vertex curr = dest;

while (curr != src) {

path[pathLength++] = curr;

curr = pred[curr];

}

path[pathLength++] = src;

// reverse path array

for (int i = 0, j = pathLength - 1; i < j; i++, j--) {

Vertex tmp = path[i];

path[i] = path[j];

path[j] = tmp;

}

free(pred);

return pathLength;

}

// bst from destination

int findPath(Graph g, Vertex src, Vertex dest, int max, int *path) {

assert(g != NULL);

int *pred = findPathBfs(g, dest, src, max);

if (pred[src] == -1) {

free(pred);

return 0;

}

int pathLength = 0;

Vertex curr = src;

while (curr != dest) {

path[pathLength++] = curr;

curr = pred[curr];

}

path[pathLength++] = dest;

free(pred);

return pathLength;

}

int compareByName(Record r1, Record r2) {

int cmp1 = strcmp(RecordGetFamilyName(r1), RecordGetFamilyName(r2));

if (cmp1 != 0) return cmp1;

int cmp2 = strcmp(RecordGetGivenName(r1), RecordGetGivenName(r2));

if (cmp2 != 0) return cmp2;

return RecordGetZid(r1) - RecordGetZid(r2);

}

if curr == NULL return 0

leftDepth = recursive to left

rightDepth = recursive to right

if leftDepth >= rightDepth -> return leftDepth + 1

else return rightDepth + 1

int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return -1; // Height of an empty node is -1 (or 0 depending on the definition)
    }
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

int getDepth(BSTree root, int data, int depth) {
    if (root == NULL) {
        return -1; // Node not found
    }
    if (root->value == data) {
        return depth;
    }
    int leftDepth = getDepth(root->left, data, depth + 1);
    int rightDepth = getDepth(root->right, data, depth + 1);
    // If the node is not in the current subtree, return -1
    if (leftDepth == -1 && rightDepth == -1) {
        return -1;
    }
    // Return the maximum depth found in the current subtree
    return (leftDepth > rightDepth) ? leftDepth : rightDepth;
}

bool hasPathSum(struct TreeNode* root, int targetSum) {

if (root == NULL) {

return false;

}

bool answer = false;

int sumLeft = targetSum - root->data;

if (sumLeft == 0 && root->left == NULL && root->right == NULL) {

return true;

}

if (root->left) {

answer = answer || hasPathSum(root->left, targetSum);

}

if (root->right) {

answer = answer || hasPathSum(root->left, targetSum);

}

}

/* C program to check if a tree is height-balanced or not */

#include <stdio.h>

#include <stdlib.h>

#define bool int

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node {

int data;

struct node* left;

struct node* right;

};

/* Returns the height of a binary tree */

int height(struct node* node);

/* Returns true if binary tree with root as root is

* height-balanced */

bool isBalanced(struct node* root)

{

/* for height of left subtree */

int lh;

/* for height of right subtree */

int rh;

/* If tree is empty then return true */

if (root == NULL)

return 1;

/* Get the height of left and right sub trees */

lh = height(root->left);

rh = height(root->right);

if (abs(lh - rh) <= 1 && isBalanced(root->left)

&& isBalanced(root->right))

return 1;

/* If we reach here then tree is not height-balanced */

return 0;

}

/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* returns maximum of two integers */

int max(int a, int b) { return (a >= b) ? a : b; }

/* The function Compute the "height" of a tree. Height is

the number of nodes along the longest path from the root

node down to the farthest leaf node.*/

int height(struct node* node)

{

/* base case tree is empty */

if (node == NULL)

return 0;

/* If tree is not empty then height = 1 + max of left

height and right heights */

return 1 + max(height(node->left), height(node->right));

}

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(int data)

{

struct node* node

= (struct node*)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return (node);

}

// Driver code

int main()

{

struct node* root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

root->left->left->left = newNode(8);

if (isBalanced(root))

printf("Tree is balanced");

else

printf("Tree is not balanced");

getchar();

return 0;

}

// C program to implement optimized delete in BST.

#include <stdio.h>

#include <stdlib.h>

struct Node {

int key;

struct Node *left, *right;

};

// A utility function to create a new BST node

struct Node* newNode(int item)

{

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

temp->key = item;

temp->left = temp->right = NULL;

return temp;

}

// A utility function to do inorder traversal of BST

void inorder(struct Node* root)

{

if (root != NULL) {

inorder(root->left);

printf("%d ", root->key);

inorder(root->right);

}

}

/* A utility function to insert a new node with given key in

* BST */

struct Node* insert(struct Node* node, int key)

{

/* If the tree is empty, return a new node */

if (node == NULL)

return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)

node->left = insert(node->left, key);

else

node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;

}

/* Given a binary search tree and a key, this function

deletes the key and returns the new root */

struct Node* deleteNode(struct Node* root, int k)

{

// Base case

if (root == NULL)

return root;

// Recursive calls for ancestors of

// node to be deleted

if (root->key > k) {

root->left = deleteNode(root->left, k);

return root;

}

else if (root->key < k) {

root->right = deleteNode(root->right, k);

return root;

}

// We reach here when root is the node

// to be deleted.

// If one of the children is empty

if (root->left == NULL) {

struct Node* temp = root->right;

free(root);

return temp;

}

else if (root->right == NULL) {

struct Node* temp = root->left;

free(root);

return temp;

}

// If both children exist

else {

struct Node* succParent = root;

// Find successor

struct Node* succ = root->right;

while (succ->left != NULL) {

succParent = succ;

succ = succ->left;

}

// Delete successor. Since successor

// is always left child of its parent

// we can safely make successor's right

// right child as left of its parent.

// If there is no succ, then assign

// succ->right to succParent->right

if (succParent != root)

succParent->left = succ->right;

else

succParent->right = succ->right;

// Copy Successor Data to root

root->key = succ->key;

// Delete Successor and return root

free(succ);

return root;

}

}

/* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

bool areIdentical(struct TreeNode* root, struct TreeNode* subRoot) {

if (root == NULL && subRoot == NULL) {

return true;

}

if (root == NULL || subRoot == NULL) {

return false;

}

return (root->val == subRoot->val

&& areIdentical(root->left,subRoot->left)

&& areIdentical(root->right, subRoot->right));

}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {

if (subRoot == NULL) {

return true;

}

if (root == NULL) {

return false;

}

if (areIdentical(root, subRoot)) {

return true;

}

return isSubtree(root->left,subRoot) || isSubtree(root->right, subRoot);

}

/* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

int total(struct TreeNode* root) {

if (root == NULL) {

return 0;

}

return 1 + total(root->left) + total(root->right);

}

void preOrder(struct TreeNode* root, int sort[], int *index) {

if (root == NULL) {

return;

}

sort[(*index)++] = root->val;

preOrder(root->left, sort, index);

preOrder(root->right, sort, index);

}

int findMinDiff(int sort[], int index, int numNode) {

int min_diff = abs(sort[0]-sort[1]);

for (int i = 0; i < numNode; i++) {

for (int j = i + 1; j < numNode; j++) {

int x = abs(sort[i] - sort[j]);

if (min_diff > x) {

min_diff = x;

}

}

}

return min_diff;

}

int getMinimumDifference(struct TreeNode* root){

int numNode = total(root);

int *sort = malloc(sizeof(int) * numNode);

int index = 0;

preOrder(root, sort, &index);

return findMinDiff(sort, index, numNode);

}

ideas

- using in-order traversal and sort tree

- get the first value from the sorted array (most smallest value in tree)

int nodeCount (struct node root) {

if (root == NULL) {

return 0;

}

return 1 + nodeCount(root->left) + nodeCount(root->right);

}

/* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

bool isValidBST(struct TreeNode* root) {

if (root == NULL) {

return true;

}

if (root->left != NULL && root->val <= root->left->val) {

return false;

} else if (root->right != NULL && root->val >= root->right->val) {

return false;

}

bool answer = false;

answer = answer || isValidBST(root->right);

answer = answer || isValidBST(root->left);

return answer;

}

/* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

void traverse (struct TreeNode* root, int low, int high, int *sum) {

if (root == NULL) {

return;

}

if (root->val >= low && root->val <= high) {

*sum += root->val;

}

traverse(root->left, low, high, sum);

traverse(root->right, low, high, sum);

// do not use parameter as &sum for recursion

}

int rangeSumBST(struct TreeNode* root, int low, int high){

int sum = 0;

traverse(root, low, high, &sum);

return sum;

}

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

struct TreeNode* searchBST(struct TreeNode* root, int val){

struct TreeNode* find = root;

while(find){

if(val < find->val)

find = find->left;

else if(val > find->val)

find = find->right;

else

return find;

}

return find;

}

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

void traverse(struct TreeNode *root, int *sum) {

if (root == NULL) {

return;

}

if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {

*sum += root->left->val;

}

traverse(root->left, sum);

traverse(root->right, sum);

}

int sumOfLeftLeaves(struct TreeNode* root){

int sum = 0;

traverse(root, &sum);

return sum;

}

Right rotation:

- Root's left subtree becomes the new root

- The right child of the new root becomes the left child of the old root.

Left rotation:

- The root's right subtree becomes the new root

- The new root's left child becomes the right child of the old root.

return the new root

Pseudocode for insertion at root:

insertAtRoot(tree, item):

root = get root of "tree"

if tree is empty:

tree = new node containing item

else if item < root's value:

(tree's left child) = insertAtRoot((tree's left child), item)

tree = rotateRight(tree)

else if item > root's value:

(tree's right child) = insertAtRoot((tree's right child), item)

tree = rotateLeft(tree)

return tree

Pseudocode for tree partitioning based on an index (determined by an in order traversal)

partition(tree, index)

m = # nodes in the tree's left subtree

if index < m:

(tree's left subtree) = partition(tree's left subtree, index)

tree = rotateRight(tree)

else if index > m:

(tree's right subtree) = partition(tree's right subtree, index - m - 1)

tree = rotateLeft(tree)

return tree

left rotation :
    swaping with the right child
    new = o.l
    t2 = new.r
    new.r = o
    o.l = t2
right ratation:
    swaping with the left child
imbalance can only occur fromt the 3rd level onwards
    grandchild:
        left left root to right
        right right root to left
        lefr right parent to the left and root to right
        right left parent to the right and root to left
BST : 
left than root right greater than root
balance BST:
abs(heightdifference) <= 1
AVL tree:
for every node, the heights of the left and right subtrees differ by at most 1




TreeJoin(TreeNode* tree1, TreeNode* tree2) { 
if (tree1 == NULL) 
     return tree2;
if (tree2 == NULL) 
     return tree1;
 TreeNode* current = tree2;
 TreeNode* parent = NULL;
 while (current->left != NULL) {
 parent = current;
 current = current->left;
 }
 if (parent != NULL) {
 parent->left = current->right;
 current->right = tree2;
 }
 current->left = tree1;
 return current;
}

getHeight(root):

  If root is NULL: Return 0
  leftHeight = getHeight(root->left)
  rightHeight = getHeight(root->right)
  Return 1 + (max of leftHeight and rightHeight)
 eachLevel(root, l):
 If root is NULL: Return
 If l is 1: Print root->data
 Call eachLevel(root->left, l - 1)
 Call eachLevel(root->right, l - 1)
 levelOrder(root):
 h = getHeight(root)
 For i from 0 to h:
  Call eachLevel(root, i)
  

TreeNode* increaBST (struct TreeNode* root){ 
if (root == NULL) return NULL;
struct TreeNode * newRoot = NULL; 
     struct TreeNode * leftTree = increaBST(root->left);
     root->left = NULL;
     struct TreeNode * rightTree = increaBST(root->right); newRoot = leftTree;
 if (newRoot == NULL) {
 newRoot = root;
 } else {
 struct TreeNode* temp = newRoot;
 while (temp->right != NULL) {
 temp = temp->right;
 }
 temp->right = root;
 } root->right = rightTree; 
return newRoot;
}

minDiffUtil(t, targetLevel, *prevValue, *minDiff, currentLevel): 
If t is NULL: Return 0 
If currentLevel is equal to targetLevel: 
If *prevValue is not INT_MIN: 
    diff = absolute difference between t->key and prevValue 
    *minDiff = minimum of minDiff and diff 
*prevValue = t->key 
Return 1 
left = call minDiffUtil(t->left, targetLevel, prevValue, minDiff, currentLevel + 1) 
right = call minDiffUtil(t->right, targetLevel, prevValue, minDiff, currentLevel + 1) 
Return left or right 
minDiff(t, level): 
prevValue = INT_MIN 
minDiff = INT_MAX If 
minDiffUtil(t, level, &prevValue, &minDiff, 0): 
    minDiff == INT_MAX ? 0 : minDiff;
 Return 0

function countNodes(root)
    if root is null
        return 0
    end if
    return 1 + countNodes(root.left) + countNodes(root.right)
end function
function maxDiffHelper(*root, *maxDiff)
    if root is null
        return 0
    end if
    leftNodes = countNodes(root.left)
    rightNodes = countNodes(root.right)
    // Compute the absolute node difference for the current node
    absNodeDiff = absolute value of (leftNodes - rightNodes)
    // Update the maximum node difference if this one is greater
    *maxDiff = (*maxDiff > absNodeDiff) ? *maxDiff : absNodeDiff;
    // Recursively traverse the left and right subtrees
    maxDiffHelper(root.left, maxDiff)
    maxDiffHelper(root.right, maxDiff)
    return absNodeDiff
end function
function maxDiff(*t)
    maxDiff = 0 // Initialize the maximum absolute node difference
    maxDiffHelper(t, &maxDiff)
    return maxDiff
end function

newRoot = null
    // Recursive left subtree
    leftTree = increasingBST(root.left)
    root.left = null
    // Recursive right subtree
    rightTree = increasingBST(root.right)
    // If leftTree is not null, traverse to the rightmost node
    newRoot = leftTree
    if newRoot is null
        newRoot = root
    else
        temp = newRoot
        while temp.right is not null
            temp = temp.right
        end while
        temp.right = root
    end if
    root.right = rightTree
    return newRoot

terminology

• level of a node = path length from root to node (0, 1, 2, etc.)
• height of a tree = max. path length from root to leaf (counting edges, not nodes)
  
• weight-balanced = for all nodes, equal no. of nodes on left/right subtree (helps with searching)
  
• height-balanced = as close as possible to each side of tree having same height
  

traversal methods

• inorder = numerical order → visit left subtree, then root, then right subtree
• preorder = move down columns, printing as you go → visit root, then left subtree, then right subtree
• postorder = move up columns, printing child before parent → visit left subtree, then right subtree, then root
• level order = one row at a time, left to right → visit root, then all its children, then all their

time complexity (inserting into linked list)

reasons for use

• binary search is much quicker than linear search (better for large number sets)
• binary search is easy on ordered array BUT maintaining ordered array is hard (have to constantly shuffle values)
• maintaining ordered linked list is easy (direct insertion of values) BUT binary searching a linked list is hard (have to move linearly along list)
• SO binary search trees combine best parts of linked lists + ability to easily jump to a value

(12)

Tree TreeCopy(Tree t, int depth) {
 if (depth < 0) {
 return NULL;
 }
 if (t == NULL) {
 return NULL; 
 }
 struct node* newNode = malloc(sizeof(struct node));
 newNode->left = NULL;
 newNode->right = NULL;
 newNode->value = t->value;
 newNode->left = TreeCopy(t->left, depth - 1);
 newNode->right = TreeCopy(t->right, depth - 1);
 return newNode;
}

int TreeSize(Tree t) {
    if (t == NULL) {
        return 0;
    }
    return 1 + TreeSize(t->left) + TreeSize(t->right);
}
bool TreeIsPerfectlyBalanced(Tree t) {
    if (t == NULL) {
        return true;
    }
    int leftSize = TreeSize(t->left);
    int rightSize = TreeSize(t->right);
    if (abs(leftSize - rightSize) > 1) {
        return false;
    }
    return TreeIsPerfectlyBalanced(t->left) && TreeIsPerfectlyBalanced(t->right);
}

void inOrderTraversal(BSTree t, int* count, int k, int* result) {
 if (t == NULL) {
 return;
 }
 inOrderTraversal(t->left, count, k, result);
 (*count)++;
 if (*count == k) {
 *result = t->value;
 return;
 }
 inOrderTraversal(t->right, count, k, result);
}

int BSTreeGetKth(BSTree t, int k) {
 int count = -1;
 int result = -1;
 inOrderTraversal(t, &count, k, &result);
 return result;
}

Balanced Binary Tree

• a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1. (by not more than means: <=)
• Conditions
  • difference between the left and the right subtree for any node is not more than one
  • the left subtree is balanced
  • the right subtree is balanced
  
  
  Reference: https://www.programiz.com/dsa/balanced-binary-tree

Inorder Traversal:

In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.

1. Traverse the left subtree, i.e., call Inorder(left->subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right->subtree)

Preorder Traversal:

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on an expression tree.

1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left->subtree)
3. Traverse the right subtree, i.e., call Preorder(right->subtree)

Postorder Traversal:

Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.

1. Traverse the left subtree, i.e., call Postorder(left->subtree)
2. Traverse the right subtree, i.e., call Postorder(right->subtree)
3. Visit the root

Level Order Traversal

For each node, first, the node is visited and then its child nodes are put in a FIFO queue. Then again the first node is popped out and then its child nodes are put in a FIFO queue and repeat until the queue becomes empty.

Reference: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

TreeDelete(t,item):
|  Input  tree t, item
|  Output t with item deleted
|
|  if t is not empty then          // nothing to do if tree is empty
|  |  if item < data(t) then       // delete item in left subtree
|  |     left(t)=TreeDelete(left(t),item)
|  |  else if item > data(t) then  // delete item in left subtree
|  |     right(t)=TreeDelete(right(t),item)
|  |  else                         // node 't' must be deleted
|  |  |  if left(t) and right(t) are empty then 
|  |  |     new=empty tree                   // 0 children
|  |  |  else if left(t) is empty then
|  |  |     new=right(t)                     // 1 child
|  |  |  else if right(t) is empty then
|  |  |     new=left(t)                      // 1 child
|  |  |  else
|  |  |     new=TreeJoin(left(t),right(t))  // 2 children
|  |  |  end if
|  |  |  free memory allocated for t
|  |  |  t=new
|  |  end if
|  end if
|  return t

int TreeSumOdds(Tree t) {
    if (t == NULL) {
        return 0;
    } else if (t->value % 2 != 0) {
        return t->value + TreeSumOdds(t->left) + TreeSumOdds(t->right);
    } else {
        return TreeSumOdds(t->left) + TreeSumOdds(t->right);
    }
}

static int depthHelper(BSTree t, int key, int count) {
    if (t == NULL) {
        return -1; 
    }
    if (t->value == key) {
        return count;
    }
    if (key < t->value) {
        return depthHelper(t->left, key, count + 1);
    } else {
        return depthHelper(t->right, key, count + 1);
    }
}
int BSTreeNodeDepth(BSTree t, int key) {
    return depthHelper (t, key, 0);
}

BST - O(h) for search, insert, and delete where h is the height of the tree.

AVL - O(log(n)) for search, insert, and delete

binary search tree

min height - log2(n) where n is number of nodes

search - O(log2(n))

insertion - O(log2(n))

space - O(n) (each node has three thingys)

traversal

depth first search

pre-order - root, left, right

post-order - left, right, root

in-order - left, root, right

level-order/breadth first search - order that the nodes are visited in.

partition(tree, i) - rearranges tree so that element with index i becomes root

//Checks if it is the same tree
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //empty tree both are the same 
    if (p == NULL && q == NULL) {
        return true;
    }
    //one tree is empty 
    if (p == NULL || q == NULL) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    } else {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
}
// Returns true if there is a subtree
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL) {
        return false;
    } else if (isSameTree(root, subRoot)) {
        return true;
    } else {
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
}

int bstHeight(struct node *t) { 
    if (t == NULL) { 
        return -1; 
    } else { 
        int lh = bstHeight(t->left); 
        int rh = bstHeight(t->right); 
        if (lh > rh) { 
            return lh + 1; 
        } else { 
            return rh + 1; 
        } 
    } 
}

1. If the current node (say temp ) is a 4 node that node is split. The following is the way used for splitting a node:
   1. Erase the mid-value (say X ) of the node and store it.
   2. Now split the remaining 3 node into two 2 nodes .
   3. If the temp was the root of the tree, then create another root (a 2 node ) with the value X which have the newly split nodes as its child.
   4. Otherwise, add the value X accordingly in the parent node. (As we are always splitting the 4 nodes while moving from top to bottom, it is guaranteed that there will always be a space available in the parent).
   5. Now arrange those two 2 nodes accordingly with the parent node.
2. Find the child whose interval contains the value which is being inserted in the tree.
3. If the child is a leaf node then insert the value. Otherwise, descend to the child and repeat from step 1

Say we have to insert the following numbers in the tree:
{10, 20, 30, 40, 50, 60}

Insert 10:
=> As there is nothing currently, insert 10 in a new root.
=> The root is a 2 node.

Insert 20:
=> Insert 20 in the root (which is also the leaf) in a sorted manner.
=> The root is now a 3 node.

Insert 30:
=> Insert 30 in the root (which is also the leaf) in a sorted manner.
=> The root is now a 4 node

Insert 40:
=> Now the root is a 4 node. So this need to be splitted.
=> So the new root will be 20. The two child will be 10 and 30.
=> Now, add 40 with the node containing 30.

Insert 50:
=> The node 50 needs to be inserted to the right of 20.
=> Is is added with the node having values 30 and 40.
=> This leaf now becomes a 4 node.

Insert 60:
=> While searching for path, we will encounter the node with values 30, 40, 50.
=> Split this node. Add 40 to the parent and arrange the other two nodes accordingly.
=> Now insert 60 in the node with value 50.

Relevant Properties of 2-3-4 Trees:

All Operations Take O(LogN) time complexity

Perfectly balanced

Can be mapped to a red black tree

Balancing BSTs

How to stop trees from getting too imbalanced

• Tree rotations
• Insertions at root
• Tree partitioning

When inserting into BST:

Best case when balanced:

• Tree height log(n)
• Search cost O(log(n))

Worst case ascending/descending order such imbalanced:

• Tree height O(n)
• Search cost O(n)

Weight balanced for all nodes, abs(nodes left subtree - nodes right subtree) < 2

Height balance for all nodes, abs(height left subtree - height right subtree) < 2

Tree rotation

Cheap O(1)

Simple localised pointer arrangement

If leaf to root

Cost is O(height)

Payoff is improved balance = reduced height

Pushes search cost towards O(logn)

Insertion at root

Insert new node as leaf normally in tree, then lift new node to top by rotation

Recently inserted items are closer to root and lower cost

But needs large scale re-arrangement of tree O(h) complexity but cost is doubled in reality since need to travel down then up the tree

Higher tendency to be balanced but not guaranteed

For applications where the same element is looked up many times, you can only consider moving a node to the root when it's found during a search

Makes lookup for recent items very fast

Tree partitioning

Rearranges tree so element with index 1 becomes root. Index are based on in-order Partitioning the middle index often makes things more balanced Complexity similar to insert at root. The faster the closer to the root

Periodic rebalancing

A simple approach to using partition selectively. Rebalance the tree every k inserts Only issue is we need number of nodes which is a O(n) traversal

Trees are connected graphs that have edges (lines) and nodes (circles)

No cycles

Each node has a particular value

Each node connects with up to k children

Binary search trees are able to be searched with a binary search, and are easy to maintain/modify.

1. Binary search is a necessary algorithm for large sets of numbers
2. Maintaining an ordered array is hard, but binary searching is easy
3. Maintaining an ordered link list is easy, but binary searching is hard

BSTs provide the best of both world

• When ordered, their structure is a binary search flow
• And it's easy to make modifications

BSTs are ordered trees, so

• Each node is the root of 2 subtrees (which could be null)
• All in the left subtree are less than root
• All in right subtee are greater than root

Binary search trees are either

• Empty
• Consist of node with two subtrees
  • Node contains valie
  • Left and right subtrees are also BSTs

Level - Path length from root to node

Height/Depth - Max path length from root to leaf

Balanced BSTs, when there's equal number of nodes on the left and right subtrees

Traversal:

• Preorder: Visit root, left subtree, then right subtree
• Inorder: Visit left subtree, root, then right subtree
• Postorder: Visit left subtree, right subtree, then root
• Level order: Visit root, its children, and all their children

the node labelled root is the old root and the node labelled pivot becomes the new root.

beta is the "dont lose me" variable from sims lectures