Question

Write a routine to list out the nodes of a binary tree in level-order. List the...

Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You must do this in linear time. Prove your time bound (Java)

Homework Answers

Answer #1

/*If you have any query do comment in the comment section else like the solution*/

This can be done using a FIFO queue, in which left and right child of a parent node will be pushed in the queue, each node will be pushed and popped from the queue only once, hence the time complexity will be O(n)

void levelOrderTraversal(Node root) 
{     
    if(root == null) 
        return;       
    Queue<Node> q =new LinkedList<Node>();       
    q.add(root);                    
    while(q.size() > 0) 
    {                                   
        Node node = q.peek(); 
        q.remove();
        System.out.print(node.data + " ");            
        if(node.lt != null) 
            q.add(node.lt); 
        if(node.rt != null) 
            q.add(node.rt);                       
    } 
}
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Maximum how many nodes can there be in a complete Binary Tree with level h? (java...
Maximum how many nodes can there be in a complete Binary Tree with level h? (java programing)
Suppose a binary tree stores integers. Write efficient methods (and give their Big-Oh running times) that...
Suppose a binary tree stores integers. Write efficient methods (and give their Big-Oh running times) that take a reference to a binary tree root T and compute a. the number of nodes with two children that contain the same value **JAVA**
Given the list of values below, create a Binary Search Tree for the list, Use the...
Given the list of values below, create a Binary Search Tree for the list, Use the first value in the list as the root of the tree, add the nodes to BST in the order they appear in the list.[50, 44, 82, 39, 35, 98, 87, 100, 74, 23, 34, 14, 94] What is the minimum height of a Binary Tree that contains 24nodes? What is the minimum height of a Binary Tree that contains 64nodes? What is the minimum...
How can I prove that any node of a binary search tree of n nodes can...
How can I prove that any node of a binary search tree of n nodes can be made the root in at most n − 1 rotations?
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
A binary tree isfullif every non-leaf node has exactly two children. For context, recallthat we saw...
A binary tree isfullif every non-leaf node has exactly two children. For context, recallthat we saw in lecture that a binary tree of heighthcan have at most 2h+1−1 nodes, and thatit achieves this maximum if it iscomplete, meaning that it is full and all leaves are at the samedistance from the root. Findμ(h), theminimumnumber of nodes that a full tree of heighthcan have, and prove your answer using ordinary induction onh. Note that tree of height of 0 isa single...
This is in java and you are not allowed to use Java API classes for queues,...
This is in java and you are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them. You should construct a BST by inserting node values starting with a null tree. You can re-use the code for the insert method given in the sample code from the textbook. -insert method is provided below Your code should have a menu driven user interface at the command line with...
Write code in java Implement a method to build an AVL tree out of a sorted...
Write code in java Implement a method to build an AVL tree out of a sorted (ascending order) array of unique integers, with the fastest possible big O running time. You may implement private helper methods as necessary. If your code builds a tree that is other than an AVL tree, you will not get any credit. If your code builds an AVL tree, but is not the fastest big O implementation, you will get at most 12 points. You...
Write a C++ recursive function that counts the number of nodes in a singly linked list....
Write a C++ recursive function that counts the number of nodes in a singly linked list. (a) Test your function using different singly linked lists. Include your code. (b) Write a recurrence relation that represents your algorithm. (c) Solve the recurrence relation using the iterating or recursive tree method to obtain the running time of the algorithm in Big-O notation.
This assignment involves using a binary search tree (BST) to keep track of all words in...
This assignment involves using a binary search tree (BST) to keep track of all words in a text document. It produces a cross-reference, or a concordance. This is very much like assignment 4, except that you must use a different data structure. You may use some of the code you wrote for that assignment, such as input parsing, for this one. Remember that in a binary search tree, the value to the left of the root is less than the...