4 ms·

This actually seems like a pretty simple problem, to be honest, where the obvious solution is the best one. Inverting a binary tree means reversing the order o

This actually seems like a pretty simple problem, to be honest, where the obvious solution is the best one. Inverting a binary tree means reversing the order of the sequence of elements that it represents. Thus inverting a binary tree is simply swapping the left and right edge of every node recursively down the tree. You could do this with a recursive algorithm by modifying the tree in-place or by constructing a new tree. I don’t see any obvious candidate optimizations other than the fact that it’s straightforward to do in place (e.g. using std::swap in C++, or mem::swap in Rust). However I don’t think this is as good of an interviewing question as other potential questions. See my other comment in the thread for one that I think is better. The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. Better questions (IMO) are tasks that professional software engineers are likely to encounter while doing their job at the company — or representations of them, while testing knowledge of A&DS as necessary. Even if a company does particularly a lot of work with binary trees, then that company would be likely to have number of such A&DS already implemented. If you’re working at Google then I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them; undoubtedly these implementations already exist within their standard libraries. Personally, I can’t immediately ever recall encountering a binary tree in business logic while working as a professional engineer. I wouldn’t expect to unless I was building some thing like a collections library or a specialized solution to a large scale problem like implementing a novel data store of some kind. And if I was doing that kind of work I’d break out references (e.g. Knuth as a starting point, and any relevant recent research), and review open source software for comparison or as a candidate for directly solving the problem (SQLite, MySQL/InnoDB, LevelDB & BDB, Apache Commons libraries, etc.)

WalterBright 5y ago
> The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. I'm not so sure. One aspect is even recognizing that the task can be done by a known algorithm. Not knowing the algorithms may make one mistakenly believe that the opportunity to apply algorithms never came up. > I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them I'm sorry, they are so trivial it takes more work to understand the documentation on the library one than it takes to just do it. Though personally, if a candidate flunked the binary tree question, but had a very successful project, I'd take a closer look before rejecting him. For one thing, I'd want to have a look at the project's source code. I'd also want to verify he'd actually written the code for that project.
- jcrites 5y ago
  They are trivial to implement, but not desirable if you want your project to integrate with the company's existing codebase and be able to draw on a large base of preexisting algorithms. A company like Google/Facebook(Meta)/Amazon doesn't want many redundant copies of binary tree implementations per language in their code base. In general they'd want one implementation with a suite of algorithms that can operate on it. Maybe if your implementation is very specific to the task at hand it might make sense; otherwise I'd expect to use a binary tree via something like a sorted container interface. For example, in Java, something like java.util.TreeMap [1], which I understand is implemented as a binary tree. Unless you were building a compiler or data store or something very specific and optimized, I see the need for building one as unlikely. [1] https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap....
  - WalterBright 5y ago
    On the other hand, I also like to make my modules standalone, and not have 20-30 dependencies. I agree with you about things like "convert this string to a number", where it's too easy to get wrong (like not handling overflow) or be inefficient. But binary trees (and linked lists), like I said, are so trivial it is just not worth the bother.

WalterBright 5y ago

> The reason is that programming tasks like this are pretty uncommon to encounter as a professional software engineer. I'm not so sure. One aspect is even recognizing that the task can be done by a known algorithm. Not knowing the algorithms may make one mistakenly believe that the opportunity to apply algorithms never came up. > I can’t imagine that you would need to build a binary tree data structure or an algorithm for inverting them I'm sorry, they are so trivial it takes more work to understand the documentation on the library one than it takes to just do it. Though personally, if a candidate flunked the binary tree question, but had a very successful project, I'd take a closer look before rejecting him. For one thing, I'd want to have a look at the project's source code. I'd also want to verify he'd actually written the code for that project.

jcrites 5y ago
They are trivial to implement, but not desirable if you want your project to integrate with the company's existing codebase and be able to draw on a large base of preexisting algorithms. A company like Google/Facebook(Meta)/Amazon doesn't want many redundant copies of binary tree implementations per language in their code base. In general they'd want one implementation with a suite of algorithms that can operate on it. Maybe if your implementation is very specific to the task at hand it might make sense; otherwise I'd expect to use a binary tree via something like a sorted container interface. For example, in Java, something like java.util.TreeMap [1], which I understand is implemented as a binary tree. Unless you were building a compiler or data store or something very specific and optimized, I see the need for building one as unlikely. [1] https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap....
- WalterBright 5y ago
  On the other hand, I also like to make my modules standalone, and not have 20-30 dependencies. I agree with you about things like "convert this string to a number", where it's too easy to get wrong (like not handling overflow) or be inefficient. But binary trees (and linked lists), like I said, are so trivial it is just not worth the bother.