What is space complexity for breadth-first search on a binary tree?

committedandroider

Here is my Java solution for printing a binary tree level by level with breadth first search(it works!!)

public void printByLevel() {
    System.out.print("Elements By Level:");
    if(overallRoot!= null) {
        Queue<IntTreeNode> bfs = new LinkedList<IntTreeNode>();
        bfs.add(overallRoot);
        while(!bfs.isEmpty()) {
            IntTreeNode root = bfs.remove();
            System.out.print(" " + root.data);
            if(root.left!=null) 
                bfs.add(root.left);
            if(root.right!=null)
                bfs.add(root.right);
        }
    }
    System.out.println();
}

I know with my breadth-first search algorithm, I will visit all the nodes in the tree so the time complexity of the algorithm will be O(n).

I am having trouble with analyzing the space complexity of my solution though. I learned from Space Complexity that when analyzing space complexity, you have to take into account the space you allocate from the heap and the stack

Here, I am not making any recursive calls so the space complexity will just be the space I allocated for the queue for breadth-first-search. I read from here BFS Complexity that the space complexity of breadth first search is O(V) where V is the number of vertices.

Does that same space complexity apply to my tree variation? I have yet to produce a test case in which the BFS queue will hold all the nodes in the tree. Even when the binary tree degenerates to a linked list like in the following pictorial that I got from BST, where normal operations on a tree take O(n) time and O(n) space, the BFS queue will hold at most 1 element.

    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              ...`

Can anyone give me a test case in which the BFS queue will hold all the nodes in tree, proving that the space complexity is O(n)?

anatolyg

Consider the "full" or "perfect" binary tree:

     .
   / .
  0  .
 / \ .
0    .
 \ / .
  0  .
   \ .
     .

At the last iteration, the queue will hold roughly half of the nodes in the tree, so the complexity is O(n/2), which is the same as O(n).

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Time and Space Complexity for Breadth First Search

From Dev

Time and Space Complexity for Breadth First Search

From Dev

Breadth First Search on a Binary Search Tree in Python

From Dev

Space complexity of validation of a binary search tree

From Dev

Space complexity of validation of a binary search tree

From Dev

How to return a string with a Breadth First Order traversal of a binary search tree?

From Dev

Breadth First Traversal With Binary Search Tree C++

From Dev

Space complexity of iterative vs recursive - Binary Search Tree

From Dev

Breadth First Search time complexity analysis

From Dev

State Space Search: A* and Breadth First Search

From Dev

breadth first on binary tree - using Semicontext notation

From Dev

Space/Time complexity of Binary Tree Equality

From Dev

How do i calculate space complexity for checking if binary search tree is balanced?

From Dev

How do i calculate space complexity for checking if binary search tree is balanced?

From Dev

Time Complexity of breadth first search with adjacency matrix representation?

From Dev

Running time complexity for binary search tree

From Dev

Time complexity of deletion in binary search tree

From Dev

GATE 2008: Time Complexity of Binary Search Tree

From Dev

Time complexity of deletion in binary search tree

From Dev

breadth of a binary tree

From Dev

Depth First Search on a Binary Tree

From Dev

Time/Space Complexity of Depth First Search

From Dev

Building a Binary Tree (not BST) in Haskell Breadth-First

From Dev

What's the space complexity of a radix tree?

From Dev

What's the space complexity of a radix tree?

From Dev

Spanning tree out of graph using Breadth First Search?

From Java

What is the time-complexity in a binary search?

From Dev

What would be time Complexity of binary search algorithm?

From Dev

Efficiency of Breadth First Search

Related Related

  1. 1

    Time and Space Complexity for Breadth First Search

  2. 2

    Time and Space Complexity for Breadth First Search

  3. 3

    Breadth First Search on a Binary Search Tree in Python

  4. 4

    Space complexity of validation of a binary search tree

  5. 5

    Space complexity of validation of a binary search tree

  6. 6

    How to return a string with a Breadth First Order traversal of a binary search tree?

  7. 7

    Breadth First Traversal With Binary Search Tree C++

  8. 8

    Space complexity of iterative vs recursive - Binary Search Tree

  9. 9

    Breadth First Search time complexity analysis

  10. 10

    State Space Search: A* and Breadth First Search

  11. 11

    breadth first on binary tree - using Semicontext notation

  12. 12

    Space/Time complexity of Binary Tree Equality

  13. 13

    How do i calculate space complexity for checking if binary search tree is balanced?

  14. 14

    How do i calculate space complexity for checking if binary search tree is balanced?

  15. 15

    Time Complexity of breadth first search with adjacency matrix representation?

  16. 16

    Running time complexity for binary search tree

  17. 17

    Time complexity of deletion in binary search tree

  18. 18

    GATE 2008: Time Complexity of Binary Search Tree

  19. 19

    Time complexity of deletion in binary search tree

  20. 20

    breadth of a binary tree

  21. 21

    Depth First Search on a Binary Tree

  22. 22

    Time/Space Complexity of Depth First Search

  23. 23

    Building a Binary Tree (not BST) in Haskell Breadth-First

  24. 24

    What's the space complexity of a radix tree?

  25. 25

    What's the space complexity of a radix tree?

  26. 26

    Spanning tree out of graph using Breadth First Search?

  27. 27

    What is the time-complexity in a binary search?

  28. 28

    What would be time Complexity of binary search algorithm?

  29. 29

    Efficiency of Breadth First Search

HotTag

Archive