binary-tree

Binary Tree

• root, child, left child and right child, height of tree, nodes at level, inorder, preporder, postorder, Depth fierst traversal, breadth first traversal, level order travsersal, single threaded and double threaded BT, pointing to inorder predecessor and successor,

• Inorder traverse

function inorderTraversal(node){    if node is not null:    inorderTraversal(node.left)    print(node.value)    inorderTraversal(node.right)}

• inorder traverse using stack

function inOrderTraversal(root){    stack = []      result = []    current = root     while current is not null or stack is not empty:        while current is not null:            stack.push(current)            current = current.left        current = stack.pop()        result.push(current.value)        current = current.right    return result}

• In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.thats why there is space required to traverse.

• to print current level, recusrsion; for Level order tarvesral - can use Queue to put element one by one and pop OR use recursion

function printNthLevel(root, n){    if root is null:        return    if n is 1:        print(root.value)    else if n > 1:        printNthLevel(root.left, n - 1)        printNthLevel(root.right, n - 1)}

• For level order traversal while using queue, Lets say in some problem we want to differentiate between levels, then either we can add a dummy data in between levels or we can use 2 queues. e.g https://www.geeksforgeeks.org/averages-levels-binary-tree/

function levelOrderTraversal(root){    if root is null: return;    queue = Queue()    queue.enqueue(root)    while queue is not empty:        current = queue.dequeue()        print(current.value)        if current.left is not null:            queue.enqueue(current.left)        if current.right is not null:            queue.enqueue(current.right)}

• if find height of a tree , recusrion (use same technique for get size of tree)

function findTreeHeight(node){    if node is null:        return -1     leftHeight = findTreeHeight(node.left);    rightHeight = findTreeHeight(node.right);    treeHeight = max(leftHeight, rightHeight) + 1;    return treeHeight;}

• inorder can be done using a stack

• inorder and (preorder or post order) can uniquely identify a tree

• construct a tree by given preorder and inorder

• imp. convert a binary tree to threade tree using inorder and queue

• vertical order traversal, use queue and x-coordinates - https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/ (check lelevl order traversal approach)

• for ith node, it will have (2i+1) and (2i+2) as children.