tree and linked list

https://oscarforner.com/2016/02/26/Prefix_trees__Comparison_between_Trie__Ternary_Search_Tree_and_Radix_Tree

Tree_and_Radix_Tree

Binary tree

number of nodes in full BT: 2**(h+1)+1

number of leaf nodes: 2**h

number of leaf nodes in the full BT with n elements : (n+1)/2.

http://www.techiedelight.com/dfs-interview-questions/

http://www.geeksforgeeks.org/wp-content/uploads/Tree-Traversal.png

deep copy of binary tree

Find the longest path from a leaf to leaf (diameter of tree)

https://blogs.ncl.ac.uk/andreymokhov/walking-on-trees/ diameter of tree

http://www.zrzahid.com/binary-tree-all-paths-max-sum-path-diameter-longest-path-shortest-path-closest-leaf/

http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

def diameter_height(node):
if node is None: return 0, 0
ld, lh = diameter_height(node.left)
rd, rh = diameter_height(node.right)
return max(lh + rh + 1, ld, rd), 1 + max(lh, rh)

def find_tree_diameter(node):
d, _ = diameter_height(node)
return d

http://www.java67.com/2016/10/how-to-print-leaf-nodes-of-binary-tree-without-recursion-in-java.html

http://algorithms.tutorialhorizon.com/given-two-binary-trees-check-if-one-binary-tree-is-a-subtree-of-another/

import java.util.*;

public class BinaryTree {

//reference to root of the binary tree

public Node root;

//Node as an inner class

public class Node{

int data; //integer value that this Node holds

Node left,right; //references to left and right binary sub-trees

//constructor with the value that the node holds is passed

public Node(int data){

this.data=data;

left=null;

right=null;

}

public Node(){ //default constructor without any arguments

this.left=null;

this.right=null;

}

}

//checks if tree rooted at root1 is subtree of tree rooted at root2

public boolean isSubTree(Node root1, Node root2){

if(root1==null || root2==null)

return root1==null && root2==null;

Node n1 = searchNode(root2, root1.data);

if(n1==null)

return false;

return areEqual(root1,n1);

}

//returns the node of tree with given key

public Node searchNode(Node root,int key){

if(root==null)

return null;

if(root.data==key)

return root;

Node leftAns = searchNode(root.left,key),rightAns = searchNode(root.right,key);

return leftAns!=null ? leftAns : rightAns;

}

//checks if tree rooted at root1 and tree rooted at root2 are identical(both in terms of structure and keys)

public boolean areEqual(Node root1,Node root2){

if(root1==null || root2==null)

return root1==null && root2==null;

return root1.data==root2.data && areEqual(root1.left,root2.left) && areEqual(root1.right,root2.right);

}

}

Pseudocode for spiral level order traversal of a binary tree.

//Define two stacks S1, S2
//At each level, S1 carries the nodes to be traversed in that level S2 carries the child nodes of the nodes in S1 spiralLevelOrder(root) {
S1 = new Stack()
S2 = new Stack()
S1.push(root)
spiralLevelOrderRecursion(S1, S2, 1)
}
spiralLevelOrderRecursion(S1, S2, level) {
while(S1 not empty) {
node = S1.pop()
visit(node)
if (level is odd) {
S2.push(node.rightNode)
S2.push(node.leftNode)
} else {
S2.push(node.leftNode)
S2.push(node.rightNode)
}
}

if (S2 not empty)
spiralLevelOrderRecursion(S2, S1, level+1)
}

Sample tree : 1-(2-(4,5),3-(5,6)) format : root-(leftchild, rightchild)

Applying the pseudocode :

spiralLevelOrderRecursion([1], [], 1)

S2 - [] -> [3] -> [2, 3] visit order : 1

spiralLevelOrderRecursion([2,3], [], 2)

S2 - [] -> [4] -> [5,4] -> [6, 5, 4] -> [7, 6, 5, 4] visit order : 2, 3

spiralLevelOrderRecursion([7,6,5,4], [], 3)

visit order : 7, 6, 5, 4

void writeBinaryTree(BinaryTree *p, ostream &out) {

if (!p) {

out << "# ";

} else {

out << p->data << " ";

writeBinaryTree(p->left, out);

writeBinaryTree(p->right, out);

}

}

void readBinaryTree(BinaryTree *&p, ifstream &fin) {

int token;

bool isNumber;

if (!readNextToken(token, fin, isNumber))

return;

if (isNumber) {

p = new BinaryTree(token);

readBinaryTree(p->left, fin);

readBinaryTree(p->right, fin);

}

}

There is only one kind of breadth-first traversal--the level order traversal.

http://incolumitas.com/2015/01/24/implementing-two-graph-traversal-algorithms-in-python-depth-first-search-and-breadth-first-search/

To implement a level-order traversal, we need a first-in first-out queue

http://www.leetcode.com/2010/09/printing-binary-tree-in-level-order.html

http://www.ibm.com/developerworks/aix/library/au-aix-stack-tree-traversal/index.html

https://workshape.github.io/visual-graph-algorithms/

#include< iostream >

#include"Queue.h"

struct BinaryTree{

int data;

BinaryTree *left;

BinaryTree *right;

} *root=NULL;

BreadthOrderTraversal(BinaryTree root){

Queue< BinaryTree *> Q;

BinaryTree temp;

Q.Enqueue(root);

while(!Q.isEmpty()){

temp = Q.Deque(); //Deque the topmost node of the tree

if (temp->left) Q.Enqueue(temp->left); //Enqueue if exists

if (temp->right) Q.Enqueue(temp->right); //Enqueue if exists

}

}

if we will use the stack instead queue in code above we will have Depth First Traversal:

DepthFirstInorderTraversal(Tree *p){

stack < Tree* > S;

do{

while (p!=NULL) {

S.push(p); // store a node in the stack

p=p->left; // visit it's left child

}

// If there are nodes in the stack to which we can move up then pop it

if (!S.empty()){

p=S.top();

S.pop();

cout << p->ele << "-"; // print the nodes value

p=p->right; // vistit the right child now

}

}while(!S.empty()||p!=NULL); // while the stack is not empty or there is a valid node

}

http://habrahabr.ru/post/259295/ Dikstra поиск кратчайших путей из данной вершины в графе.

Reverse singly-linked list

http://jasonroell.com/2015/07/06/every-programmer-should-understand-thi-s/

public class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

/ /using Recursion

public ListNode reverseList(ListNode head) {

if(head==null || head.next == null)

return head;

//get second node

ListNode second = head.next;

//set first’s next to be null head.next = null;

ListNode rest = reverseList(second);

second.next = head;

return rest;

}

// without using Recursion

public ListNode reverseList(ListNode head) {

if(head==null || head.next == null)

return head;

ListNode p1 = head;

ListNode p2 = head.next;

head.next = null;

while(p1!= null && p2!= null){

ListNode t = p2.next;

p2.next = p1;

p1 = p2;

if (t!=null){

p2 = t;

}else{

break;

}

}

return p2;

}

Reverse Linked List

http://www.leetcode.com/2010/04/reversing-linked-list-iteratively-and.html

#include <stdio.h>

typedef struct Node {

char data;

struct Node* next;

} Node;

void print_list(Node* root) {

while (root) {

printf("%c ", root->data);

root = root->next;

}

printf("\n");

}

Node* reverse(Node* root) {

Node* new_root = 0;

while (root) {

Node* next = root->next;

root->next = new_root;

new_root = root;

root = next;

}

return new_root;

}

int main() {

Node d = { 'd', 0 };

Node c = { 'c', &d };

Node b = { 'b', &c };

Node a = { 'a', &b };

Node* root = &a;

print_list(root);

root = reverse(root);

print_list(root);

return 0;

}

Intersection point of 2 Linked Lists

Find the length of both the linked list and check that they have the same tail node.

Find the difference in length (d)

For the longer LL, traverse d nodes and check the addresses with another LL

http://codesam.blogspot.com/2011/03/check-if-two-singly-linked-lists.html

If two singly linked list intersect, then End point must be same element!

So, in list1 you can keep move until you meet the null (last element),

then keep the previous node. Same work for list2.

Then compare end_node_list1, end_node_list2

Find if the linked list has a loop:

http://codesam.blogspot.com/2011/03/algorithm-to-determine-if-linked-list.html

http://www.geeksforgeeks.org/archives/112

Have 2 pointers moving with different speed

def has_loop?(node)

slow = node

fast = node

until slow.next.nil? or fast.next.nil? do

slow = slow.next

fast = fast.next.next

return true if (slow == fast)

end

false

end