BST - Index
Common Operations on BST Understanding functions of BST – insert, size and traversal Deleting a node from BST Implementing a BST in C Traversals are covered seperately below.
Traversal in BST: Inorder, pre order and post order traversal(recursive approach)
Inorder, pre order and post order traversal(iterative approach)
Level order traversal
Threaded binary tree
DFS and BFS on tree
Given the expression tree, calculate the expression
Construct a tree, given its inorder and pre-order
[Read More]
Threaded binary tree
Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.
[Read More]
Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.
For Inorder And Preorder traversals
inorder = g d h b e i a f j c preorder = a b d g h e i c f j
Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, “a” is the root of the tree; “gdhbei” are in the left subtree; “fjc” are in the right subtree. “b” is the next root; “gdh” are in the left subtree; “ei” are in the right subtree.
[Read More]
Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.
The code below prints the paranthesized form of a tree.
**print_infix_exp(node * root)** { if(root) { printf("("); infix_exp(root->left); printf(root->data); infix_exp(root->right); printf(")"); } }
Creating a binary tree for a postfix expression
`
*node create_tree(char postfix[])
{
node *temp, *st[100];
int i,k;
char symbol;
for(i=k=0; (symbol = postfix[i])!=’\0’; i++)
{
temp = (node *) malloc(sizeof(struct node));//temp = getnode();
temp->value = symbol;
temp->left = temp->right = NULL;
if(isalnum(symbol))
st[k++] = temp;
[Read More]
First / Lowest common ancestor (LCA) of 2 node in binary tree
Problem
Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Case 2- What will you do if it is Binary search tree
Example
So for example look into below figure:
So for node 4 and 14, LCA is 8.
[Read More]
Pre Order traversal - Recursive and Iterative solution
Example
Consider the tree:
div class="separator” style="clear: both; text-align: center;“>
To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
Recursive solution
preorder(N \*root) { if(root) { printf("Value : \[%d\]", root->value); preorder(root->left); preorder(root->right); } } Iterative solution
[Read More]
Find the median in a continous stream of numbers
Problem
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
OR
You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time)
**OR **
[Read More]
tree1.h fully updated
//We will do following Functions:
1. lookup
2. Insert
3. printTree,printPost, printPre
4. Selection Function
5. Delete(Hence implemented - child0,child1,child2, inorder2 functions)
#ifndef TREE1_H
#define TREE1\_H ``` ``` \# include <stdio.h> # include <stdlib.h>
#define isChildless(p) p->left==NULL &&p->right==NULL enum BOOL{false,true} ;
typedef enum BOOL BOOL; ``` ``` struct node { int data;
struct node\* left; struct node* right;
} ; typedef struct node node;
/*
Given a binary tree, return true if a node with the target data is found in the tree.
[Read More]
Deleting a node from a Binary Search Tree
Suppose we want to delete a node k. First we need to search for the node k. Offcourse k should not be null.
Then we have three cases:
1. The node to be deleted has no children - The memory occupied by this node must be freed and either the left link or the right link of the parent of this node must be set to NULL.
2. The node to be deleted has exactly one child -
[Read More]