Everything about Binary Tree and its all traversal techniques (recursive and itterative) with examples

- 
package org.dpq.ds.tree;import java.util.Stack;public class Tree<T>{    public static void main(String[] args) {        TreeNode<Integer> root = new TreeNode<Integer>(1);        root.setLeft(new TreeNode<Integer>(2));        root.setRight(new TreeNode<Integer>(3));        root.getLeft().setLeft(new TreeNode<Integer>(4));        root.getLeft().setRight(new TreeNode<Integer>(5));        root.getRight().setLeft(new TreeNode<Integer>(6));        root.getRight().setRight(new TreeNode<Integer>(7));        Tree<Integer> tree = new Tree<Integer>();        //Tree//         1//        / \//       2   3//      /\   /\//     4  5 6  7        //expected result for inorder(LNR) 4 2 5 1 6 3 7        //expected result for preorder(NLR) 1 2 4 5 3 6 7        //expected result for preorder(NLR) 4 5 2 6 7 3 1        System.out.println("recursive inorder \n");        tree.inOrder(root);        System.out.println("recursive preOrder \n");        tree.preOrder(root);        System.out.println("recursive postOrder \n");        tree.postOrder(root);        System.out.println(" preOrder Iterative \n");        tree.preOrderIterative(root);        System.out.println(" preOrder Iterative Another \n");        tree.preOrderIterativeAnother(root);        System.out.println(" inOrder Iterative \n");        tree.inOrderIterative(root);        System.out.println(" POSTOrderIterative \n");        tree.postOrderIterative(root);    }    void postOrderIterative(TreeNode<T> root){        if(root == null) return;        Stack<TreeNode<T>> stack1 = new Stack<>();        Stack<TreeNode<T>> stack2 = new Stack<>();        TreeNode<T> current = root;        stack1.push(current);        while( !stack1.empty() ){            current = stack1.pop();            stack2.push(current);            if(current.getLeft() != null) stack1.push(current.getLeft());            if(current.getRight() != null) stack1.push(current.getRight());        }        while(!stack2.isEmpty()) System.out.print(stack2.pop().getData());    }    void inOrderIterative(TreeNode<T> root){        if(root == null) return;        Stack<TreeNode<T>> stack = new Stack<>();        TreeNode<T> current = root;        while(current!=null || !stack.empty()){            while(current!=null){                stack.push(current);                current = current.getLeft();            }            current = stack.pop();            System.out.print(current.getData());            current=current.getRight();        }    }    void preOrderIterativeAnother(TreeNode<T> root){        if(root == null) return;        Stack<TreeNode<T>> stack = new Stack<>();        TreeNode<T> current = root;        while(current!=null || !stack.empty()){            while(current!=null){                System.out.print(current.getData());                if(current.getRight() != null) stack.push(current.getRight());                current = current.getLeft();            }            if(!stack.empty()) current = stack.pop();        }    }    void preOrderIterative(TreeNode<T> root){        if(root == null) return;        Stack<TreeNode<T>> stack = new Stack<>();        stack.push(root);        while(!stack.empty()){            TreeNode<T> myNode = stack.peek();            System.out.print(myNode.getData());            stack.pop();            if(myNode.getRight() != null) stack.push(myNode.getRight());            if(myNode.getLeft() != null) stack.push(myNode.getLeft());        }    }    void postOrder(TreeNode<T> root){        if(root == null) return;        postOrder(root.getLeft());        postOrder(root.getRight());        System.out.print(root.getData()+" ");    }    void inOrder(TreeNode<T> root){        if(root == null) return;        inOrder(root.getLeft());        System.out.print(root.getData()+" ");        inOrder(root.getRight());    }    void preOrder(TreeNode<T> root){        if(root == null) return;        System.out.print(root.getData()+" ");        preOrder(root.getLeft());        preOrder(root.getRight());    }}class TreeNode<T> {    private T data;    private TreeNode<T> left;    private TreeNode<T> right;    public TreeNode(T data){        this.data = data;    }    public TreeNode<T> getLeft() {        return left;    }    public void setLeft(TreeNode<T> left) {        this.left = left;    }    public TreeNode<T> getRight() {        return right;    }    public void setRight(TreeNode<T> right) {        this.right = right;    }    public T getData() {        return data;    }    @Override    public String toString() {        return "TreeNode{" +                "data=" + data +                ", left=" + left +                ", right=" + right +                '}';    }}

Popular posts from this blog

How to change column name in Dataframe and selection of few columns in Dataframe using Pyspark with example

-
Input details: #● File has json records #● Each record has fields: #○ user_id #○ card_num #○ merchant #○ category #○ amount #○ ts ### Below analysis to be done Sample data: +------+--------+---------+--------+----------+-------+|amount|card_num| category|merchant| ts|user_id|+------+--------+---------+--------+----------+-------+| 243| C_108| food| M_102|1579532902| U_104|| 699| C_106|cosmetics| M_103|1581759040| U_103|| 228| C_104| children| M_110|1584161986| U_103| Solution: from pyspark.sql.functions import col # this can be done without using window function creditCardData = spark.read.json(“card_transactions.json”) useridMaxSpendDF = df.groupby(‘user_id’).max(‘amount’) useridMaxSpendDF=useridMaxSpendDF.withColumnRenamed(“max(amount)”,”max_amount”) useridMaxSpendDF=useridMaxSpendDF.withColumnRenamed(“user_id”,”m_user_id”) cond = [creditCardData.user_id == useridMaxSpen...
Read more

What is Garbage collection in Spark and its impact and resolution

-
Image
Garbage Collection Spark runs on the Java Virtual Machine (JVM). Because Spark can store large amounts of data in memory, it has a major reliance on Java’s memory management and garbage collection (GC). Therefore, garbage collection  (GC) can be a major issue that can affect many Spark applications. Common symptoms of excessive GC in Spark are: Slowness of application Executor heartbeat timeout GC overhead limit exceeded error Spark’s memory-centric approach and data-intensive applications make it a more common issue than other Java applications. Thankfully, it’s easy to diagnose if your Spark application is suffering from a GC problem. The Spark UI marks executors in red if they have spent too much time doing GC. Spark executors are spending a significant amount of CPU cycles performing garbage collection. This can be determined by looking at the “Executors” tab in the Spark application UI. Spark will mark an executor in  red  if the executor has spent more than 10% of the time in gar...
Read more

Credit Card Data Analysis using PySpark (how to use auto broadcast join after disabling it)

-
Input details: #● File has json records #● Each record has fields: #○ user_id #○ card_num #○ merchant #○ category #○ amount #○ ts ### Below analysis to be done Sample data: +------+--------+---------+--------+----------+-------+|amount|card_num| category|merchant| ts|user_id|+------+--------+---------+--------+----------+-------+| 243| C_108| food| M_102|1579532902| U_104|| 699| C_106|cosmetics| M_103|1581759040| U_103|| 228| C_104| children| M_110|1584161986| U_103| Application: Here we will disable auto broadcast and then join 2 data frames and will see execution plan which should use broadcast join Solution: from pyspark.sql import SparkSession from pyspark.sql.functions import broadcast spark = SparkSession.builder.master(‘local[2]’)\ .appName(‘RDD_Methods_Examples’)\ .getOrCreate() print(spark.conf.get(“spark.sql.autoBroadcastJoinThreshold”)) spark.conf.set(“spark.sql.autoBroadcastJoinThreshold”, -1) pr...
Read more