PYTHON

tree traversal

# Depth First Traversals: 
(a) Inorder (Left, Root, Right) 
(b) Preorder (Root, Left, Right)  
(c) Postorder (Left, Right, Root) 

tree traversal

const breadthFirstTraversal = (root) => {
  if (root === null) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current.data);
    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }
  return result;
};

tree travers

const depthFirstTraversal = (root) => {
  if (root === null) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const current = stack.pop();
    result.push(current.data);
    if (current.right) stack.push(current.right);
    if (current.left) stack.push(current.left);
  }
  return result;
};

inorder traversal of tree

//*******this is a C program for implementation and searching in A BT*******
#include<stdlib.h>
#include <stdio.h>

struct BinaryTree{
    int data;
    struct BinaryTree*right;
    struct BinaryTree*left;
};

struct BinaryTree*createnode(int val){
    struct BinaryTree*root=(struct BinaryTree*)malloc(sizeof(struct BinaryTree));
    root->data=val;
    root->left=NULL;
    root->right=NULL;
    
}

void inorder(struct BinaryTree*root){
    if(root==NULL){
    return;
    }
    else {inorder(root->left);
    printf("%d->",root->data);
    inorder(root->right);
}

}
 
void preorder(struct BinaryTree*root){
    if(root==NULL){
        return;
    }
    else {
        printf("%d->",root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct BinaryTree*root){
    if(root==NULL){
        return;
    }
    else{
        postorder(root->left);
        postorder(root->right);
        printf("%d->",root->data);
    }
}
int main()
{
    printf("Lets grow the tree
");
    struct BinaryTree*root=createnode(1);
    root->left=createnode(2);
    root->right=createnode(3);
    root->left->left=createnode(4);
    root->left->right=createnode(5);
    
    printf("tree has grown up
");
    
    printf("Inorder traversal ");
    inorder(root);printf("NULL");

    printf("
preorder traversal ");
    preorder(root);printf("NULL");
    
    printf("
Postorder  traversal");
    postorder(root);printf("NULL");
    
    return 0 ;
}

Tree traversal

A tree is a graph whose degree of node== # of it's children & is acyclic 
Binary tree is a tree with each node having atmost 2 children.
2 ways to traverse each node once:
BFS - level wise
DFS - BY RECURSIVELY TRAVERSING ROOT,LEFT SUBTREE (L) & RIGHT SUBTREE (R)
NOTE: THERE ARE 3! WAYS OF DOING A DFS, BASED ON ORDER OF Root,L,R.     
but only 3 are useful :
Root,L,R- preorder traversal 
L,Root,R- inorder traversal 
L,R,Root- postorder traversal

Tree: Postorder Traversal

def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print(root, end = " ")

how to perform in_order traversal of a binary tree

class Node:
     def __init__(self,data):
          self.data = data
          self.parent = None
          self.left = None
          self.right = None

     def __repr__(self):
          return repr(self.data)

     def add_left(self,node):
         self.left = node
         if node is not None:
             node.parent = self

     def add_right(self,node):
         self.right = node
         if node is not None:
             node.parent = self
'''
Example:
          _2_
        /       
       7         9
      /          
     1   6         8
         /        / 
       5   10   3   4
'''
def create_tree():
    two = Node(2)
    seven = Node(7)
    nine = Node(9)
    two.add_left(seven)
    two.add_right(nine)
    one = Node(1)
    six = Node(6)
    seven.add_left(one)
    seven.add_right(six)
    five = Node(5)
    ten = Node(10)
    six.add_left(five)
    six.add_right(ten)
    eight = Node(8)
    three = Node(3)
    four = Node(4)
    nine.add_right(eight)
    eight.add_left(three)
    eight.add_right(four)

    # now return the root node
    return two

def pre_order(node):
    print(node)
    if node.left:
        pre_order(node.left)
    if node.right:
        pre_order(node.right)

def in_order(node):
    if node.left:
        in_order(node.left)
    print(node)
    if node.right:
        in_order(node.right)

def post_order(node):
    if node.left:
        post_order(node.left)
    if node.right:
        post_order(node.right)
    print(node)

if __name__ == "__main__":
    root = create_tree()
    print("
Pre-order traversal:")
    pre_order(root)
    print("
In-order traversal:")
    in_order(root)
    print("
Post-order traversal:")
    post_order(root)

binary tree traversal

//BINARY TREE TRAVERSAL
//---------------------


public class traversal{
    
    
    public static void main(String[] args) {
        treetraversal t = new treetraversal();
        
        t.root = new node('A'); // initializing the root node
        t.root.left = new node('B'); // initializing the left node
        t.root.right = new node('C'); // initializing the right node
        
        t.root.left.left = new node('D'); // initializing the sub-left node of the left node
        t.root.left.right = new node('E'); // initializing the sub-right node of the left node
        
        t.root.right.left = new node('F'); // initializing the sub-left node of the right node
        t.root.right.right = new node('G'); // initializing the sub-right node of the right node
        
        //this tree can be made as large as the we want it to be by adding further sub nodes
        
        System.out.println("IN ORDER TRAVERSAL");
        t.InOrderTraversal(t.root);
        System.out.println();
        System.out.println();

        System.out.println("PRE ORDER TRAVERSAL");
        t.PreOrderTraversal(t.root);
        System.out.println();
        System.out.println();
        
        System.out.println("POST ORDER TRAVERSAL");
        t.PostOrderTraversal(t.root);
    }
}

class node{ //as there are nodes in trees
    char key;//as every node has a value or key
    node left,right;//as every node will have a left and a right child

    node(char KEY){
        this.key = KEY;
    }
}

class treetraversal{
    /*there are thre types of traversals
    1. InOrder Traversal
    2. PreOrder Traversal
    3.PostOrder Traversal
    */

    node root;//as every tree has a root node to which there exist left and right nodes
    
        void InOrderTraversal(node n){
            //InOrder Traversal = Left Root Right
            if(n!=null){
                InOrderTraversal(n.left);
                System.out.print(n.key + " ");
                InOrderTraversal(n.right);
            }
        }

    void PreOrderTraversal(node n){
        //PreOrder Traversal = Root Left Right
        if(n!=null){
            System.out.print(n.key + " ");
            PreOrderTraversal(n.left);
            PreOrderTraversal(n.right);
        }
    }
    
    void PostOrderTraversal(node n){
        //PostOrder Traversal = Left Right Root
        if(n!=null){
            PostOrderTraversal(n.left);
            PostOrderTraversal(n.right);
            System.out.print(n.key + " ");
        }
    }
}

How to perform in-order traversal of a binary tree?

/*
	This is an implementation that collects the 
	values of the nodes of a binary tree by performing 
	an in-order traversal of the tree.

	Let n be the number of binary tree nodes
	Time complexity: O(n) 
	Space complexity: O(n)
*/
import java.util.List;
import java.util.ArrayList;

public class BTInOrderTraversal {
	private BTNode BTRoot;
	public BTInOrderTraversal() {
		/*
		 * Create tree below:
		 * 1
		 * 
		 * 2
		 * /
		 * 3
		 */
		BTRoot = new BTNode(1, null, null);
		BTNode rootRight = new BTNode(2, null, null);
		BTRoot.right = rootRight;
		BTNode rootRightLeft = new BTNode(3, null, null);
		rootRight.left = rootRightLeft;
	}
	public static void main(String[] args) {
		BTInOrderTraversal application = new BTInOrderTraversal();
		List<Integer> values = application.inorderTraversal();
		System.out.println(values); // [1, 3, 2]
	}
	// Perform in-order traversal through the tree.
	public List<Integer> inorderTraversal() {
		List<Integer> list = new ArrayList<>();
		populateList(BTRoot, list);
		return list;
	}
	// Helper method to populate list by performing
	// in-order traversal through the tree.
	private void populateList(BTNode root, List<Integer> list) {
		if (root == null) {
			return;
		}
		if (root.left != null) {
			populateList(root.left, list);
		}
		list.add(root.val);
		if (root.right != null) {
			populateList(root.right, list);
		}
	}
	// Class representing a binary tree node
	// with pointers to value, left, and right nodes
	private class BTNode {
		int val;
		BTNode left;
		BTNode right;
		public BTNode(int val, BTNode left, BTNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}

inorder traversal

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        return dfs(root, list);
    }
    private List<Integer> dfs(TreeNode root, List<Integer> list)
    {
        if(root == null)
            return list;
        list = dfs(root.left, list);
        list.add(root.val);
        return dfs(root.right,list);
    }
}

Inorder traversal Algorithm for binary tree

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Tree: Inorder Traversal

def inOrder(root):
    if root:
        inOrder(root.left)
        print(root, end = " ")
        inOrder(root.right)        
        

Preorder, inorder & postorder traversal code

class Node:
    def __init__(self, k):
        self.left = None
        self.right = None
        self.key = k


def inorder(root):
    if root != None:
        inorder(root.left)
        print(root.key)
        inorder(root.right)


# Driver Code

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.right.left = Node(40)
root.right.right = Node(50)

inorder(root)

# time complexity (using recurrence tree method)  - O(n)
where, 
n == total nodes 
# space complexity - O(height of tree)
Note: height can be both n (if each node has exactly 1 child) and 
log(n) (if every node has exactly 2 children).

# IMP NOTE : FOR PREORDER AND POSTORDER JUST ORDER OF STATEMENTS CHANGE

for ex:
below is preorder & postorder traversal with same time & space complexity as inorder

def preorder(root):
    if root == None:
        return
    print(root.key)
    preorder(root.left)
    preorder(root.right)

def postorder(root):
    if root == None:
        return
    preorder(root.left)
    preorder(root.right)
    print(root.key)