We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
Its time for a new Challenge. But before that, last weeks answer. Well the answer could have been summed up by saying just traverse in reverse and return the second node . There were a few interesting answers among them Jonathan Gilbert’s who was the first to answer correctly:
This seems pretty simple to me. An in-order traversal can be reversed by simply following the right child first and the left child last. This produces a mirror-image. In this mirror image, the second-to-last from a regular traversal becomes the second item found. Thus, carrying a small amount of state with us so we know when to stop and return with what we’ve got:
public int Value;
public TreeNode LeftChild, RightChild;
public TreeNode FindSecondToLastInOrder()
int skip = 1;
return find_second_to_last(ref skip);
private TreeNode find_second_to_last(ref int skip)
// Check the right child, if we have one.
if (RightChild != null)
TreeNode ret = RightChild.find_second_to_last(ref skip);
// If we’ve got something, skip went to 0 within the right child.
if (ret != null)
// We’re yielding a node. Normally this would return it to some
// external consumer, but in this case, we simply count this node
// and return it if we’ve reached the desired count.
if (skip == 0)
// Check the left child, if we have one.
if (LeftChild != null)
return LeftChild.find_second_to_last(ref skip);
// If we weren’t the last node in the in-order traversal and we
// don’t have a left child, return null to continue the hunt.
Ohter correct answers were from: Kris Warkentin, Michael Mrozek, Daniel Gray, Heiko Hatzfeld, Michael Dikman, Jason Kikel, Edward Shen, Bill Budge, Alex, Hugh Brown, Leppie, Configurator and Raj bhandari. Thanks to everyone, and now lets go to this weeks challenge.
This Wesek’s Question:
This week question is pretty easy. Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. According to those rules, one of the numbers is missing and you are asked to provide the most efficient method to find that missing number. Notice that you can’t allocate another helper list, the amount of memory that you are allowed to allocate is O(1). Don’t forget to mention the complexity of your algorithm…
As always you may post the solution in your blog or comment. Comments will be approved next week.
Tags :ArraychallengeIn Orderjob interviewquestionTraverseTreeNode
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd