GeekInterview.com
  I am new, Sign me up!
 
GeekInterview.com  >  Interview Questions  >  Programming  >  C
Go To First  |  Previous Question  |  Next Question 
 C  |  Question 348 of 453    Print  
Given the values of two nodes in a *binary search tree*, write a c
program to find the lowest common ancestor. You may assume that both
values already exist in the tree.

The function prototype is as follows:
int FindLowestCommonAncestor(node* root,int value1,int value)

20
/
8 22
/
4 12
/
10 14

I/P : 4 and 14
O/P : 8

(Here the common ancestors of 4 and 14, are {8,20}.
Of {8,20}, the lowest one is 8).
One of the solution can be to find out postorder traversal taking each node one by one. This postorder function should return true if both the values (v1 & v2) are found in the postorder traversal of the given node. NOTE: The given tree is a BST.... think over it......


  
Total Answers and Comments: 1 Last Update: August 03, 2007     Asked by: vipin gupta 
  
 Sponsored Links

 
 Best Rated Answer

No best answer available. Please pick the good answer available or submit your answer.
January 01, 2008 00:29:42   #1  
kaushalgoa Member Since: December 2007   Contribution: 7    

RE: Given the values of two nodes in a *binary search tree*, write a cprogram to find the lowest common ancestor. You may assume that bothvalues already exist in the tree.The function prototype is as follows:int FindLowestCommonAncestor(node* root,int val
int is_greater(int x int y)
{
if(x > y)
return 1;
else
return 0;

}

int FindLowestCommonAncestor(node* root int value1 int value2)
{
int ret;

if( (root->data value1 ) ||(root->data value2))
return -1; /* this means that one of the values is same as root->data*/
else
{
if( ((is_greater(root->data value1) && (is_greater(value2 root->data))) ) || ((is_greater(value1 root->data) && (is_greater(root->data value2))) ))
ret root->data; /* either value1 or value2 are lower and higher than root->data and vice versa*/
else if( is_greater(root->data value1) && is_greater(root->data value2) && ( (root->left->data ! value1 ) ||(root->left->data ! value2)))
ret FindLowestCommonAncestor(root->left value1 value2); /*Both value1 and value2 are lower than root->data*/
else if( is_greater( value1 root->data) && is_greater( value2 root->data) && ((root->right->data ! value1 ) ||(root->right->data ! value2)))
ret FindLowestCommonAncestor(root->right value1 value2); /*Both value1 and value2 are higher than root->data*/
else
ret root->data; /* Either root->left->data or root->right->data is equal to one of the values*/


};

return ret;
}

// Please correct me if I am wrong. Mail me on kaushalgoa @ gmail . com .

 
Is this answer useful? Yes | No

 Related Questions

A goto statement implements a local jump of program execution, and the longjmp() and setjmp() functions implement a nonlocal, or far, jump of program execution. Generally, a jump in execution of any kind 
Latest Answer : using the normal goto statement we can move only within the function. it is not possible to go from one function to another function.using setjmp and longjmp you can move from one function to another function. but it is very bad programming. since the ...

An lvalue was defined as an expression to which a value can be assigned. Is an array an expression to which we can assign a value? The answer to this question is no, because an array is composed of several 
Latest Answer : Array is not an lvalue..Eg.int arr[5] = {"1","2",.......};here arr[5] has  memory address and now we are assinging values to this.if we write arr[5]; in any function then it will not show any error, mean array does required lvalue ...

Some operating systems (such as UNIX or Windows in enhanced mode) use virtual memory. Virtual memory is a technique for making a machine behave as if it had more memory than it really has, by using disk 
Latest Answer : First of all there is a one sentence definition of Page Thrashing (I believe someone posted a similar answer here):Page Thrashing only comes about when you use Virtual Memory which requires an MMU and "fools" a process into believing that it ...

The register modifier hints to the compiler that the variable will be heavily used and should be kept in the CPU’s registers, if possible, so that it can be accessed faster. There are several restrictions 
Latest Answer : If a variable is defined by using register modifier it tells to the compiler that the variable is used repetedly and that variable executes fastly. Generally register variables are defined in loop counters. This variable stored in CPU registers and access ...

The volatile modifier is a directive to the compiler’s optimizer that operations involving this variable should not be optimized in certain ways. There are two special cases in which use of the 

Yes. The const modifier means that this code cannot change the value of the variable, but that does not mean that the value cannot be changed by means outside this code. For instance, in the example in  
Latest Answer : But isnt like the constant variables will be stored by in ROM (read only memory).Then how can the some process other than the code can change the value of const volatile ...

For integral types, on a machine that uses two’s complement arithmetic (which is just about any machine you’re likely to use), a signed type can hold numbers from –2(number of bits – 
Latest Answer : Consider the 3 bitsFor signed int these 3 bits contains both positive and negative valuesyou can find max and min values as follows-2 ^ ( n-1 ) to ( 2 ^ ( n-1 ) - 1 ) ie,  n is no. of bits-4, -3, -2, -1, 0, 1, 2, 3For unsigned int you can find the ...

A type cast should not be used to override a const or volatile declaration. Overriding these type modifiers can cause the program to fail to run correctly. A type cast should not be used to turn a pointer 
Latest Answer : we should not cast the big datatype to smaller one. Like from double to float long to integer. TIn these cases there will be chance of loosing the valuable data itself. ...

The benefit of using the const keyword is that the compiler might be able to make optimizations based on the knowledge that the value of the variable will not change. In addition, the compiler will try 
Latest Answer : A side effect benefit:Say you want to pass an argument that you do not want modified, but you do not want to pass by value.Solution pass as constant reference or pointer constant.int someFoo(myDataType const &chunkOfData);orint ...

The answer is the standard library function qsort(). It’s the easiest sort by far for several reasons: It is already written. It is already debugged. It has been optimized as much as possible (usually). 
Latest Answer : Greetings!can u plz explain me the sorting function with its implementation in a small program and send it to my e-mail Id : venki_m182003@yahoo.com ...


 Sponsored Links

 
Related Articles

Tree Topology

Tree Topology Among all the Network Topologies we can derive that the Tree Topology is a combination of the bus and the Star Topology The tree like structure allows you to have many servers on the network and you can branch out the network in many ways This is particularly helpful for colleges unive
 

Concepts of Object-Oriented Programming

Object Oriented JavaScript In this chapter you ll learn about OOP Object Oriented Programming and how it relates to JavaScript As an ASP NET developer you probably have some experience working with objects and you may even be familiar with concepts such as inheritance However unless you re already a
 

C++ Pure Virtual Function and Base Class

C Pure Virtual Function and Virtual Base Class In this C tutorial you will learn about pure virtual function declaration of pure virtual function and virtual base class virtual base class and how to implement a virtual base class explained with examples mosgoogle center What is Pure Virtual Function
 

C++ Function Passing Types

C Function Passing Types In this C tutorial you will learn about function passing types two types of arguments passing in functions passed by value  and  passed by reference are discussed here mosgoogle center The arguments passed to a function can be performed in two ways Passed
 

What is Common Metadata

In simple but technical term, metadata is a data that describes another data. It can be any item describing an individual datum or a collection of multiple content items. Metadata is very useful in facilitating the use, management and understanding of data in a large data warehouse. Depending on the
 

What is Common Data Structure

In big data warehouses such as those used by business organizations which may have many branches around the world and which may have diversified products and services, different kinds of data flood the warehouse every single day. These data may come from other warehouse data sources, or simply fresh
 

What is Common Data Modeling Method

Common Data Modeling is one of the core considerations when setting up a business data warehouse. Any serious company wanting to have a data warehouse will have to be first serious about data models. Building a data model takes time and it is not unusual for companies to spend two to five years just
 

What is Common Data Modeling

Common Data Modeling is defining the unifying the structure used in allowing heterogeneous business environments to interoperate. A Common Data Model is very critical to a business organization. Especially with business environment where it is common to have multiple applications, a Common Data Mod
 

What is Common Data Model

This data model represents events, entities and objects in the real world that are of interest to the company. It is subject oriented and includes all aspects of the real world, primarily activities pertaining to the business. To use lay terms, a data model can be considered a road map to get one em
 

What is Common Data Architecture

Business need to define their organizational rules, policies and process in order to realize their projected growth within a specified period. In order to realize these targets, the essentially need to have a basic framework as the guide in their operations. The gathering and use of data is a very s
 

About Us -  Privacy Policy -  Terms and Conditions -  Contact -  Ask Question -  Propose Category -  Site Updates 

Copyright © 2005 - 2009 GeekInterview.com. All Rights Reserved

Page copy protected against web site content infringement by Copyscape