C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
Sunday C++ interview problem. Given a binary tree, implement a column-order traversal. Each node is in a column, either -1 (left child) or +1 (right child) from its parent. Nodes in the same column should be traversed by distance from the root and by their value if the distance also matches. Solve it yourself: https://buff.ly/3iDhYL0 Solution: https://buff.ly/3H7XZ0I #cpp #cplusplus #coding #programming #dailybiteofcpp
I didn't know `std::is_eq`. It's very useful here to implement the spaceship operator. I had to implement both `operator==` and `operator<`. And using `std::set` instead of `std::vector` plus `std::sort` comes quite handy as well. Apart from that, so surprised my solution was so similar to yours. I even defined a `node_info` struct! 😂 https://compiler-explorer.com/z/xj841raEW
Just a side note, nothing to do with cpp.
just wondering about the practical use case of this problem & solution .. please post it if you know, Thanks
That's a leetcode medium question, i remember solving it there
Thanks for this post Šimon Tóth, Just for my personal record I will post here my implementation: https://github.com/carlesmartin85/cppnd/blob/main/45/src/main.cpp Personally I found it hard to understand the statement ("Nodes in the same column should be traversed by distance from the root and by their value if the distance also matches") and I sadly couldn't take the point either by reading the case statements... I, nevertheless, thought the image was quite straight forward but again I found the 'sewing rules' not quite simple to understand... Time constricted I implemented a column-based sewing where a {1,2,3,4,5,6,7} would be reordered as {4,2,5,1,6,3,7} and not as {4,2,1,5,6,3,7}... Now, before posting, I see Wentao Bi, might have taken a similar approach by pre-ordering from left to right but honestly I messed up with the original statement... surely my fault! Thanks again for your work!
Any particular website or platform you get these questions off of?
A solution in C++ is about 100 lines of code (including type definitions). A solution in Scala is 5 lines of code, short enough to be pasted here. sealed trait T[A]; final case class Leaf[A](a: A) extends T[A]; final case class Bra[A](a: A, l: T[A], r: T[A]) extends T[A]; def toListCO[A]: T[A] => List[A] = { case Leaf(a) => List(a); case Bra(a, l, r) => toListCO(l) ++ List(a) ++ toListCO(r) }; val t: T[Int] = Bra(1, Bra(2, Leaf(4), Leaf(5)), Bra(4, Leaf(6), Leaf(7))); assert(toListCO(t) == List(4, 2, 5, 1, 6, 4, 7))