DSA-workspace/tree.java at main · Hydra-Slayer/DSA-workspace · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class tree {
    public static void main(String[] args) {
        // Build the tree:
        // 1
        // / \
        // 2 3
        // / \ / \
        // 4 5 6 7
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        // bfs(root);
        System.out.println();
        dfs_pre(root);
        System.out.println();
        dfs_in(root);
        System.out.println();
        dfs_post(root);

    }

    public static void dfs_pre(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        if (root == null)
            return;
        st.add(root);
        while (!st.isEmpty()) {
            TreeNode curr = st.pop();
            System.out.print(curr.val + " ");
            if (curr.right != null) {
                st.add(curr.right);
            }
            if (curr.left != null) {
                st.add(curr.left);

            }

        }
    }

    public static void dfs_in(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !st.isEmpty()) {
            // Traverse to the leftmost node
            while (curr != null) {
                st.push(curr);
                curr = curr.left;
            }

            // Process the leftmost node
            curr = st.pop();
            System.out.print(curr.val + " ");

            // Move to the right subtree
            curr = curr.right;

        }
    }

    public static void dfs_post(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        if (root == null)
            return;
        st.add(root);
        while (!st.isEmpty()) {
            TreeNode curr = st.pop();
            System.out.print(curr.val + " ");
            if (curr.left != null) {
                st.add(curr.left);

            }
            if (curr.right != null) {
                st.add(curr.right);
            }

        }
    }

    public static void bfs(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode curr = q.poll();
            System.out.println(curr.val + " ");
            if (curr.left != null) {
                q.add(curr.left);
            }
            if (curr.right != null) {
                q.add(curr.right);
            }
            System.out.println();
        }
    }
}