Level of a node in the binary tree.

/* A tree node structure */ struct node { int data; struct node *left; struct node *right; }; /* Helper function for getLevel(). It returns level of the data if data is present in tree, otherwise returns 0. */ int getLevelUtil(struct node *node, int data, int level) { if ( node == NULL ) return

Inorder successor of a node.

Algorithm to find Inorder Successor Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not. Input: node, root // node is the node whose Inorder successor is needed. output: succ // succ is Inorder successor of node. 1) If right subtree of node is not

Find vertical sum of given binary tree.

The Below tree has 5 vertical lines Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7 We need to output: 4 2 12 3 7 We can

Print ancestor of a node.

source : Techpuzzle We have a binary tree (not BST). 1 / \ 4 5 / \ / \ 2 3 7 8 We need to print all the ancestors of 7 i.e. : 1 5 7 Apart from the Depth First Search of this tree, we can use the following recursive way to print

Intersection of two arrays.

Solution: Let’s called array1 as A and array2 as B, each with size m and n. The obvious brute-force solution is to scan through each element in A, and for each element in A, scan if that element exist in B. The running time complexity is O(m*n). Not good! Can we do better? Absolutely! First,

Iterative Inorder Binary Tree traversal.

void iterative_inorder(Node * node) { Stack s; // Initially empty while(1) { while(node) { s.push(node); node = node->left; } if(s.isempty()) break; else { Node * temp = s.pop(); printf(“%d “, temp->value); node = temp->right; } } } Better Alternative (Without modification in tree node): void in_order_traversal_iterative(BinaryTree *root) { stack <BinaryTree*> s; BinaryTree *current = root;

A sorted single linked list to a balanced BST.

As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes. Isn’t the bottom-up

Balanced BST from sorted array.

The code below creates a balanced BST from the sorted array in O(N) time (N is the number of elements in the array). Compare how similar the code is to a binary search algorithm. Both are using the divide and conquer methodology. BinaryTree* sortedArrayToBST(int arr[], int start, int end) { if (start > end) return

given binary tree is a Binary Search Tree (BST) or not.

First, you must understand the difference between Binary Tree and Binary Search Tree (BST). Binary tree is a tree data structure in which each node has at most two child nodes. A binary search tree (BST) is based on binary tree, but with the following additional properties: * The left subtree of a node contains

Max Difference between two elements in an array.

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6,