Two Java Iterative solution DFS and BFS


  • 43
    Y

    This is the iterative version of finding the depth. The recursive version is trivial, so expect the interviewer to ask for the iterative version. I used two stacks for the dfs one and a queue for the level-order traversal one. Level order one is faster.

    DFS

    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> value = new Stack<>();
        stack.push(root);
        value.push(1);
        int max = 0;
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int temp = value.pop();
            max = Math.max(temp, max);
            if(node.left != null) {
                stack.push(node.left);
                value.push(temp+1);
            }
            if(node.right != null) {
                stack.push(node.right);
                value.push(temp+1);
            }
        }
        return max;
    }
    // 7ms
    

    BFS

    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            count++;
        }
        return count;
    }
    // 3ms

  • 5
    G

    I think the first method is also BFS


  • 1
    Y

    It is DFS, just an iterative version using stack.


  • 1
    X

    @yfcheng I think both solutions are similar to level order tranversal


  • 0
    S
    This post is deleted!

  • 0
    E

    Excellent! Thank you for sharing.


  • 0

    The dfs one seems to be bfs, but it actually is dfs.Because when I look at the order of nodes that pop out of stack, the order indeed confirms to dfs.


  • 0
    A

    It's dfs, in pre order -- root -> right -> left


  • 0

    Thank you for sharing. These two algorithms are very instructive esp. for beginners.


  • 0
    L

    Excellent´╝üThanking for your sharing


  • 0
    L

    what is the time complexity and the spark complexiy of this program.


  • 0
    B

    @xuanyige Agree!! But level order transversal is general explanation. In my opinion, preorder DFS should transverse node itself first, than left node, then right node. But this code shows that the priority of the left node and right node are the same. So, this will not be a strictly defined DFS in my opinion.


  • 0
    L

    @BradyHuang It is DFS, in the beginning my opinion was same with you, but you can run a test case by hand, on the top of stack, it's always searching right node first. His two solutions, the most difference is data structure, stack is First In Last Out, which ensure the top element is latest one.


  • 0
    M
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.