• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 09:56
CET 15:56
KST 23:56
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2312[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over6Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Weekly Cups (Nov 9-15): Clem and herO take over SC4ALL: II Indiegogo Campaign Announcement No more SC2 streamers on team liquid? Team Liquid Map Contest #23 StarCraft open world shooter announced at BlizzCon
Tourneys
RSL goes to London! 2026 Offline Finals Nov 21-22 soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
The PondCast: SC2 News & Results Mutation # 552 Secret Storm Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
XUN appreciation thread BW General Discussion List of top players active on ShieldBattery Potentially helpful Shield Battery feedback. People still play BW?
Tourneys
[BSL23] Ro16 Group B - Saturday 21:00 CET 2v2v2v2 Tournament Stage 2: Players KCM Race Survival 2026 Season 4 SC1 Kevin Scrim hosted by SOOP (Nov 18-19)
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread The PlayStation 5 Stormgate/Frost Giant Megathread Warcraft III: The Frozen Throne Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread The Games Industry And ATVI Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 17386 users

[!] Help with binary search trees.

Blogs > Sinensis
Post a Reply
Sinensis
Profile Blog Joined April 2009
United States2513 Posts
November 15 2009 18:12 GMT
#1
I'm using java to create iterative traversals through binary search trees.

I have a NLR traversal here that I made: http://pastebin.com/m5c01b50

I need a RNL traversal next and I just can't figure it out. Once again, it has to be iterative, no recursion allowed. Please help.

*
onmach
Profile Blog Joined March 2009
United States1241 Posts
November 15 2009 19:14 GMT
#2
Here is some psuedocode. You will have to turn it into java yourself. Start with a variable currentNode that is set at the root and an empty node stack.

1. If there is a node to the right, push current node onto stack, follow right node (by setting it to currentNode).
2. If there is no right node, print current node.
3. If there is a left node push it onto stack. follow left node.
4. If there is no left node pop your current node from the stack. If you can't pop anything because your stack is empty, you are done.

That _should_ do it.
DeathByMonkeys
Profile Blog Joined March 2008
United States742 Posts
November 15 2009 22:22 GMT
#3
Do they have linked lists in java?
Sinensis
Profile Blog Joined April 2009
United States2513 Posts
Last Edited: 2009-11-15 23:17:49
November 15 2009 22:23 GMT
#4
edit:

The code I'm trying to implement this with is giving me nonsense output (only displays 3 nodes out of many).

I've got the pseudocode and loop to accomplish it here: http://pastebin.com/m23f256a

Any other suggestions?
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
November 16 2009 05:18 GMT
#5
you can turn recursive program to iterative program using a stack easily.

So normally if you want to write iter, or at least this is what I do, is I write a recursive one first, then try to convert it into an iterative one.

For trees, the idea of a "fringe" is crusial, make sure you understand what it is and how to use it.
Here's an overview:

A fringe is where you put your unexpanded nodes on. For instance, if you want to do a Dpth first search on a tree and print everything, you can do:

1) recursively:
define printTree(node):
......if leaf?(node)
.........print node.content
......else:
..........printTree(node.left)
..........print node.content
..........printTree(node.right)

2) iteratively:
define printTree(node):
......fringe = new Stack()
......visited = new Set()
......fringe.push(node)
......while(fringe.notEmpty())
............current = fringe.pop
............if current in visited:
..................print current.content
............else:
..................visited.add(current)
..................fringe.push(current.left)
..................fringe.push(current)
..................fringe.push(current.right)
remark: there's bit bug here where what if a node doesn't have children but whatever, the general idea is same.

So then, breadth first search is EXACTLY THE SAME except you use a Que for your fringe, and a whole sort of tree search is done with different fringe implementation, and how to use it.

In short, all tree search is done by maintaining a fringe, and deciding what/when to put in it, and how/when to take it out
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
onmach
Profile Blog Joined March 2009
United States1241 Posts
Last Edited: 2009-11-16 21:09:27
November 16 2009 21:02 GMT
#6
Looking at your pastebin, you are close, but not quite.
Since you made a good faith attempt, here is my attempt at solving this. I have no compiled this, there may still be errors, but you can see that this is pretty close.

http://pastebin.com/d3e9d837a

The idea here is you have to go right as far as you can saving each node along the way into your stack, print the node, then go left once, right as far as you can again, print node, etc. When you can no longer go right or left, you go back up (that is where the pop comes in).

I'm not a java programmer and I don't have an environment for it at work, so you'll undoubtedly have to tweak that a bit. I may have the termination condition slightly wrong, but otherwise I think that is pretty close.

Edit: Actually this will have an infinite loop. You'll have to do what the guy above me said, you will have to keep a list of nodes you have visited so that you don't revisit them. At each step of the way, if the node you want to go to is in your list of visited nodes, you pretend it is null.

Another way is to save the last node you worked on and compare that to the nodes of your current node and if it is on the right, only then do you go left and if it is on the left, you go up. That is way more efficient, but more difficult.
Please log in or register to reply.
Live Events Refresh
OSC
22:00
King of the Hill #268
Liquipedia
RSL Revival
22:00
Offline Finals: Playoffs
Clem vs SerralLIVE!
herO vs Rogue
Tasteless1857
ComeBackTV 1441
IntoTheiNu 1166
RotterdaM697
TaKeTV 453
IndyStarCraft 375
kabyraGe 179
Rex157
3DClanTV 53
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Tasteless 1857
RotterdaM 697
IndyStarCraft 375
mouzHeroMarine 318
LamboSC2 160
Rex 157
ProTech83
SHIN 29
StarCraft: Brood War
Britney 44799
Calm 8029
firebathero 1555
Horang2 840
Jaedong 475
BeSt 357
actioN 333
EffOrt 224
Hyuk 221
Soulkey 175
[ Show more ]
Zeus 131
Pusan 102
Mind 91
Hyun 76
ggaemo 59
PianO 46
Snow 45
Noble 33
Barracks 27
sSak 25
Movie 20
Bale 17
Sacsri 16
Hm[arnc] 16
zelot 15
Rock 13
yabsab 12
sOs 5
Dota 2
Gorgc6829
Dendi867
XaKoH 382
XcaliburYe168
League of Legends
KnowMe59
Counter-Strike
edward261
Super Smash Bros
Mew2King120
Heroes of the Storm
Khaldor293
Other Games
summit1g11633
singsing3258
B2W.Neo1039
Beastyqt408
febbydoto6
Organizations
Other Games
EGCTV558
StarCraft: Brood War
lovetv 8
[ Show 14 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• HerbMon 22
• Michael_bg 6
• ChaeLyn 5
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Nemesis1902
• Stunt411
Other Games
• WagamamaTV447
Upcoming Events
IPSL
2h 4m
Ret vs ggnore13
nOmaD vs Aether
BSL
5h 4m
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
8h 4m
WardiTV Weekly
21h 4m
Ultimate Battle
21h 4m
Bisu vs Light
Kung Fu Cup
1d 20h
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
2 days
The PondCast
3 days
KCM Race Survival
3 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
RSL Offline Finals
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3

Upcoming

CSL Season 23: Qualifier 1
Sector 591
YSL S4
SC4ALL II: Brood War
CSL 2026 Winter (S23) - 3v3
CSL 2026 Winter (S23)
NBSL 2026 Xiamen LAN
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.