https://www.codingame.com/training/medium/binary-search-tree-traversal
Send your feedback or ask for help here!
Created by @codingWhale,validated by @amurushkin,@BenjaminUrquhart and @JBM.
If you have any issues, feel free to ping them.
Hi @codingWhale,
I have a question regarding level order traversal with binary trees: is the definition of level order traversal to visit nodes on a level from “left” to “right” resulting in an ascending order? I could not find it in the definition on wikipedia.
My binary tree uses a generic graph data structure I programmed. This generic graph structure has implemented level order traversal, since this is a generic graph routine. But a generic graph does not know anything about “left” or “right” or “order of values” (this is part of a binary tree definition). In my case the algo runs throught the edges in the order they are created. Therefore this code goes correctly through the levels but the order of nodes depends on the creation order of edges and not on thier value. This results in some errors with your defined tests.
Well, these are only “errors”, when the definition of level order traversal with binary trees is “do traversel in ascending order on each level”. Hence my question above about the definition of level order traversal with binary trees.
Thanks in advance.
Level order traversal is just another name for BFS (breadth first search).
If not specified, it’s usually done from left to right.
If you cannot identify left and right children of a node, then your tree has a problem and you won’t be able to do anything with it.
So find a way to identify them properly.
You can use an array Left and an array Right to map a node to its left/right children, you can also use a small struct for your nodes with attributes left and right.
Another classic way is to only use one array Tree to store the tree. The root is placed at index 1, and for a given node of index i, its children are at index 2*i and 2*i+1 (which is convenient cause you can move from child to parent by dividing by 2).
Hi @pardouin,
thanks for your answer. Well, with my binary tree I can of course distinguish between left an right (otherwise I could not have solved the other order traversals, which work fine), because there I defined a boolean data type for edge values. My “problem” is, that I created an BFS iterator in my generic graph lib, which is the basis for my binary tree. What is the definition of “Left” in a generic graph, which can have multiple edges from an to a node and where the “value” of an edge can be anything?
So my question is more about the definition of BFS (is there a defintion of order for nodes on the same level, when you do a BFS?) and not that I cannot create the code to read the nodes from Left to Right on a certain level of a binary tree (I have the code in my head. Just have to implement it 
).
There’s no canonical order for BFS in a general graph, you take children as they come.
It doesn’t even have to be consistent over repetition, you can imagine that your children are stored in unordered structures for example (which is not very convenient for debuging, or measuring performance but, why not).
A binary tree is very different from a general graph (graph and tree are different), different enough to write a seperate set of template code if you want to keep your binary tree code simple and fast.
How different they are?
The number of allowed children nodes is different.
The ordering of children nodes is different.
The possibility of allowing acyclic graph is different.
The add(Node) method is different.
The search() method is different.
The traversal implementation are (due to the above many differences) different.
Hi @FoxLee,
thanks for your answer and the advise. I was reading some stuff about graphs and are now trying to learn about them in a practical way by solving codingame puzzles. Therefore my decision to use a graph structure as basis for my binary tree was kinda influenced 
.
I googled a little bit and have now an idea about a propper binary tree data structure. I will create a second implementation of this puzzle with it and out of curiosity do some performance comparisions between them.
1 Like
For anyone who is interested in this, I ran some numbers. I created 10.000 random and unique isize numbers between -10.000 and 10.000. Afterward I feeded them into my binary tree code with a propper tree data structure and my code based on my graph lib. These are the results on my labtop:
duration to add nodes to binary tree: 5.2966ms
duration to add nodes to graph: 353.8637ms
duration of iter_pre_order_traversal with binary tree: 935.8µs
duration of iter_pre_order_traversal with graph: 170.472ms
duration of iter_in_order_traversal with binary tree: 1.132ms
duration of iter_in_order_traversal with graph: 171.6084ms
duration of iter_post_order_traversal with binary tree: 981.1µs
duration of iter_post_order_traversal with graph: 178.1838ms
duration of iter_level_order_traversal with binary tree: 8.2436ms
duration of iter_level_order_traversal with graph: 366.7364ms
Thanks again for your input
100X speed up. Impressive.
Why does my Java code does not work in Java?
Obviously you got bugs.
Continuing the discussion from [Community Puzzle] Binary Search Tree Traversal:
I’m confused, I got one test failing while submitting (Small random numbers and all others are green) and I got absolutely no idea what can goes wrong 
I would be happy to know what could fail in this single scenario.
Only that validator features an input containing 0 as one of the values to insert into the binary tree. Maybe your code doesn’t handle that correctly?
1 Like