June 29, 2014

**Question:** How would you create a binary search tree?

**Answer:**

to create a tree you need a node. a node in a tree looks like

```
function Node(val){
this.value = val;
this.left = null;
this.right = null;
}
```

Create a constructor for binary search tree

```
function BinarySearchTree(){
this.root = null;
}
```

Now you need to understand the structure of a binary search tree. For every node value in the left is smaller than the value of the node and value at the right is higher than the value of the root.

so while inserting a value you have to find the appropriate location

```
BinarySearchTree.prototype.push = function(val){
var root = this.root;
if(!root){
this.root = new Node(val);
return;
}
var currentNode = root;
var newNode = new Node(val);
while(currentNode){
if(val < currentNode.value){
if(!currentNode.left){
currentNode.left = newNode;
break;
}
else{
currentNode = currentNode.left;
}
}
else{
if(!currentNode.right){
currentNode.right = newNode;
break;
}
else{
currentNode = currentNode.right;
}
}
}
}
```

```
var bst = new BinarySearchTree();
bst.push(3);
bst.push(2);
bst.push(4);
bst.push(1);
bst.push(5);
```

**Question:** How do you implement Breadth First Search

**Answer:**

```
```

ref: stackoverflow

ref: js algorithms

**Question:** How to perform in order traversal

```
function dfs(node){
if(node){
console.log(node.value);
dfs(node.left);
dfs(node.right);
}
}
```

**Question:**

**Answer:**

```
function inorder(node){
if(node){
inorder(node.left);
console.log(node.value);
inorder(node.right);
}
}
```

ref: source of image

```
//code here
```

**Question:** How can you find the min value in a bst

finding min is super simple. the go through the left node and left most node is the minimum node

```
function minNode(node){
if(!node){
return 0;
}
if(node.left){
return minNode(node.left)
}
return node.value
}
```

**Question:** How can you find the max value in a bst

```
function maxNode(node){
if(!node){
return 0;
}
if(node.right){
return maxNode(node.right)
}
return node.value;
}
```

**Question:**What is balanced and unbalanced tree

**Answer:**

- The left and right subtrees' heights differ by at most one, AND
- The left subtree is balanced, AND
- The right subtree is balanced

ref: Get answer from here

**Question:** check a binary tree is BST or not?

**Answer:**

**Step-1:** if node is null, its BST

```
function isBST(node){
if(!node){
return true;
}
if(node.left != null && node.left.value > node.value){
return false;
}
if(node.right !=null && node.right.value < node.value) {
return false;
}
if(!isBST(node.left) || !isBST(node.right)) {
return false;
}
return true;
}
```

The reason this method will generate wrong result is for

```
//use method 4 in the link below
```

**Quetion:** How could you check a tree is balanced or not

**Answer: **

check multiple example whether it is balanced. check balanced tree example

```
function height(node){
if(!node) return 0;
var leftHeight = height(node.left);
var rightHeight = height(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
```

**Question:**

**Answer:**

```
function printAncestor(node, target){
if(!node) return false
if(node.value == target) return true;
if(printAncestor(node.left, target) || printAncestor(node.rigth, target)){
console.log(node.value);
return true;
}
return false
}
```

ref: from stack overflow

this will work for bst only. If you are dealing with binary tree..this needs to be modified

```
function commonAncestor(node, n1, n2){
if(!node) return;
var val = node.value;
if(n1 < val && n2<val){
return commonAncestor(node.left, n1, n2);
}
if(n1<val && n2<val){
return commonAncestor(node.right, n1, n2);
}
console.log('lowest common ancestor value: ', val);
return node;
}
```

ref: common ancesotr

```
function commonAncestorBT(node, n1, n2){
if(!node) return;
var val = node.value;
if(n1 == val || n2 ==val){
return node;
}
var left = commonAncestorBT(node.left, n1, n2);
var right = commonAncestorBT(node.right, n1, n2);
if(left && right){
return node;
}
return (left) ? left : right;
}
```

ref: try pavels blog

ref: bst left view

ref: print right view

ref: merge two bst

ref: binary tree to bst

ref: check subtree

ref: gfg

**Question:**

**Answer:**

A binary tree whose height of the left subtree and height of the right subtree differ at most one.

**Question:**

**Answer:**

It is Self balancing binary search tree. This means in an AVL tree, heights of two child subtrees of any node differ by at most one. If at any time if heights differ more than one, re-balancing is done to restore the height balance property.

Lookup, insertion and deletion all takes O(logn) in average and worst case

**Question:**

**Answer:**A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black.

- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black. However, two black node may be adjacent
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
- Root node will always be black

ref: Red Black Trees

- check binary tree is balanced
- two nodes are cusin
- lowest common ancestor
- k th smalled node
- in order successor and precessor
- maximum path between two nodes
- all nodes of k distance
- vertical order
- nodes that doesnt have siblings
- bst to doubly linked list
- deepest left node
- check leaves
- sum of odd levels and even levels node
- isporphisom: dont know what is this
- pair with a given sum
- floor and ceil of bst
- two nodes swapped, correct bst
- check complete or not
- max width of bst
- all root to leaf path
- BST from sorted array
- From BST, linked list for each level
- check binary tree is BST
- next node (in-order successor) of BST
- First common ancestor of two nodes in BT
- Very large two BT. check one is sub tree of another
- all path that sums to a number in BT
- carzy for code list of tree questions
- geeks for geeks questions
- glassdoor questions
- you tube got some questions as well
- career cup list of question