 |  |  |  |  |  |  |  |
Finding Maximum Width of Binary Search Tree
Please support our C++ advertiser: Intel Parallel Studio Home
 |
•
•
Join Date: Mar 2008
Posts: 12
Reputation: 
Solved Threads: 0
Newbie Poster
Dear all,
I need to find the max width of Binary Search Tree. It means the biggest number of nodes in a level among all levels.
http://www.imgloadtr.com/pics/aca410...5721df328a.jpg
In the figure the maximum width is 4, since level 3 has the biggest number of nodes, which is 4.
I will be grateful, if you help me..
I need to find the max width of Binary Search Tree. It means the biggest number of nodes in a level among all levels.
http://www.imgloadtr.com/pics/aca410...5721df328a.jpg
In the figure the maximum width is 4, since level 3 has the biggest number of nodes, which is 4.
I will be grateful, if you help me..
I can think of two simple solutions off the top of my head:
1) Allocate an array of N, where N is the number of nodes in the tree. Then traverse the tree and save the level of each node in the array as you go. Sort the array and the longest run will be the level with the most nodes.
2) Perform a level-order traversal of the tree and count how many nodes are on each level. Save the largest value as you go down, and when you get to the end, you'll have the level with the most nodes.
1) Allocate an array of N, where N is the number of nodes in the tree. Then traverse the tree and save the level of each node in the array as you go. Sort the array and the longest run will be the level with the most nodes.
2) Perform a level-order traversal of the tree and count how many nodes are on each level. Save the largest value as you go down, and when you get to the end, you'll have the level with the most nodes.
I'm here to prove you wrong.
|
Other Threads in the C++ Forum
- Previous Thread: can't find the problem after checking my similar programs
- Next Thread: how to code ATM for banks
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest C++ Posts
- Today's Posts
- Unanswered Threads
api array arrays based binary c++ c/c++ calculator char char* class classes code coding compile console conversion convert count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int java lib linkedlist linker linux list loop looping loops map math matrix memory multiple news number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets
