Puzzle: First common parent

I love to come up with elegant and simple algorithms for hard problems. Recently one thought came to my mind: why don't I create a catalog of interesting puzzles that I come across. I am sure it will be useful to some people. At least to those who are preparing for an interview. So here is my first in the series.

Disclaimer: I do not claim ownership of any of these puzzles that you will see in this series, unless explicitly noted. If I know the source, I give credit to the source. If I don't know the source and you do, please drop a comment pointing me to the original source of the puzzle.

Here is the problem:
You are given a binary search tree. For the sake of simplicity, assume that each node in the binary search tree holds an integer value and all the values are unique. Each node in the binary search tree has a reference to its right child and left child, but not to its parent. Given root, and two random nodes, find the first common parent of these two nodes. In case one of them is the ancestor of the other, return the ancestor node as the common parent.
Please note that you can only perform downward traversal, as none of the nodes have a reference to its parent.

Comments

Post a Comment

Popular posts from this blog

The mysterious ORA-03111 error

Recently one of the applications that I developed started throwing exceptions, that had the following message: SQL state [72000]; error code [1013]; ORA-03111: break received on communication channel When I googled around, I couldn't come across anything useful. Sadly enough most of the sites just showed the documentation for that error, without any explanation from anyone experiencing that issues. So here you go, with the best possible explanation that I could come up with. My application sets two things on the connection that is throwing this exception: It sets the fetchSize to be 2500 rows It sets the query timeout to be 10 seconds The database server and the application are separated over a long latency network (actually there is a NetEm box that emulates the long latency between these two boxes) which has a latency characteristic of 50+/-5 milliseconds. This is the whole setup. It is important to understand how the timeout is handled by the Oracle client (in my case JDBC clien...
Read more

Note on allocationSize parameter of @SequenceGenerator while using JPA

I ran into what I thought as an issue while I was using the sequence ID generation strategy in JPA. The JPA provider I am using is Hibernate. I think sharing my experience will save someone some time. To use a sequence (For e.g. Oracle sequence) to generate values and assign them to the ID field of your persistence object, you will following something like this: @Id @Column(name = "ITEM_ID") @GeneratedValue(strategy = GenerationType.SEQUENCE, generator="ItemIdSeqGenerator") @SequenceGenerator(name="ItemIdSeqGenerator", sequenceName="ITEM_ID_SEQ", allocationSize=1) private long itemId; This means the following things: The @Id annotation says that the field itemId is a primary key. The @Column annotation says that the corresponding column in the database is ITEM_ID. The @GeneratedValue says that the value that needs to be populated in the itemId should be generated, while that object is persisted. The strategy to generate the value is to...
Read more

xVM's vboxmanage.exe command

You can view and edit the configuration of your guest OSs using the vboxmanage command. To view the list of guest OSs you have, give the following command: C:\Program Files\Sun\xVM VirtualBox>VBoxManage.exe list vms VirtualBox Command Line Management Interface Version 2.2.2 (C) 2005-2009 Sun Microsystems, Inc. All rights reserved. "MySolaris" {dc6dc85f-5583-4a1b-bf3e-969941a2cd91} "Ubuntu" {eb973bbf-d86e-4579-85eb-6ea2cd12bf95} "Debian" {3e784597-89d8-4f17-90cb-63e866c651a3} "openSUSE" {6862884e-60e1-4c65-8aab-b57ec38a3922} "Debian-Lenny" {4b561432-abac-4a27-a501-b42af956b96b} To view the specific guest, you can use the UUID of the guest. For e.g. C:\Program Files\Sun\xVM VirtualBox>VBoxManage.exe showvminfo eb973bbf-d86e-4579-85eb-6ea2cd12bf95 VirtualBox Command Line Management Interface Version 2.2.2 (C) 2005-2009 Sun Microsystems, Inc. All rights reserved. Name: Ubuntu Guest OS: Ubuntu UUID: eb973bb...
Read more