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

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

Window function in PySpark with Joins example using 2 Dataframes (inner join)

-
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

Complex SQL: fetch the users who logged in consecutively 3 or more times (lead perfect example)

-
From the login_details table, fetch the users who logged in consecutively 3 or more times. Table Name : LOGIN_DETAILS Approach : We need to fetch users who have appeared 3 or more times consecutively in login details table. There is a window function which can be used to fetch data from the following record. Use that window function to compare the user name in current row with user name in the next row and in the row following the next row. If it matches then fetch those records. –Table Structure: drop table login_details; create table login_details( login_id int primary key, user_name varchar(50) not null, login_date date); delete from login_details; insert into login_details values (101, ‘Michael’, current_date), (102, ‘James’, current_date), (103, ‘Stewart’, current_date+1), (104, ‘Stewart’, current_date+1), (105, ‘Stewart’, current_date+1), (106, ‘Michael’, current_date+2), (107, ‘Michael’, cur...
Read more