Lineal descendant in multidimensional javascript array

Question

I have a highly nested multidimensional array similar to the one below. For simplicity, I express it in json format:

[
    {
        "Object": "Car",
        "Child": [
            {
                "Object": "Toyota",
                "Child": [
                    {
                        "Object": "Prius"
                    },
                    {
                        "Object": "Yaris"
                    }
                ]
            },
            {
                "Object": "Honda",
                "Child": [
                    {
                        "Object": "Accord"
                    },
                    {
                        "Object": "Civic",
                        "Child": [
                            {
                                "Object": "Sedan"
                            },
                            {
                                "Object": "Coupe"
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

How can I determine if an object is a lineal descendant of another object?

For example, "Sedan" is a lineal descendant of "Civic", "Honda", and "Car"; but not a lineal descendant of "Coupe", "Accord", "Toyota", "Prius", or "Yaris".

I want to do something like this:

function Lineal_Descendant(A,B){
    /*do something*/
}

Lineal_Descendant("Sedan","Civic") /*return true*/
Lineal_Descendant("Sedan","Toyota") /*return false*/
Lineal_Descendant("Prius","Honda") /*return false*/
Lineal_Descendant("Yaris","Car") /*return true*/

Answer 1

First of all,

DO NOT use "Object" as a key on an Object.

You are just one small typo away from actually overwriting the native javascript Object which would unleash the javascript apocalypse. I suggest using name as an alternative.

Second, this can be solved with a pretty simple recursive function:

var find = function(obj, search){
    // return this object if it matches
    if(obj.name === search)
      return obj;
    // false if it has no children
    if(!obj.hasOwnProperty('Child')) 
      return false;
    for(var i=0,u=obj.Child.length;i<u;i++){
        // recursively check each child
        var foundRecursively = find(obj.Child[i], search);
        if(foundRecursively) // match found! return up the chain
            return foundRecursively; 
    }
    // no match, return up the chain
    return false;
};

var Lineal_Descendant = function(A,B){
    // find the B (the parent) in data, then find A in B.  
    // Negate any object to a boolean and return.
    return !!find(find(data[0],B),A);
};

Lineal_Descendant("Sedan","Civic") // true
Lineal_Descendant("Sedan","Toyota") // false
Lineal_Descendant("Prius","Honda") // false
Lineal_Descendant("Yaris","Car") // true

This solution requires the data to be an array with 1 root Object (as OP shows in the sample data). That said, it could easily be adapted to accept an array of roots to start.

Answer 2

I ended up using the concept of Modified Preorder Tree Traversal. Basically, I loop through the json object using a self-contained recursive function; and assign "left" and "right" values to each object. Once the whole json object is modified with the inclusion of "left" and "right" values, I compare the "left" and "right" values in Object A and B to see if it is a lineal descendant.

For example, if Object A is a lineal descendant of B, "left" value in A will be greater than "left" value in B, and "right" in A will be smaller than "right" in B.

Code:

var data = [{"Object":"Car","Child":[{"Object":"Toyota","Child":[{"Object":"Prius"},{"Object":"Yaris"}]},{"Object":"Honda","Child":[{"Object":"Accord"},{"Object":"Civic","Child":[{"Object":"Sedan"},{"Object":"Coupe"}]}]}]}];

alert(Lineal_Descendant(data,'Sedan','Civic'));  //true
alert(Lineal_Descendant(data,'Sedan','Toyota')); //false
alert(Lineal_Descendant(data,'Prius','Honda'));  //false
alert(Lineal_Descendant(data,'Yaris','Car'));    //true

function Lineal_Descendant(data, A, B){
    var i=1,                  //value to be assigned to "left" or "right" in modified preorder tree traversal
        k=0,                  //value to be assgined to entry index
        aIndex,               //entry index value for object A
        bIndex,               //entry index value for object B
        entry = new Array(),  //entry element
        mpttObj = mptt(data); //modified preorder tree traversal recursive function. Assign "left" and "right" value.

    function mptt(obj) {
        for (var f=0, n=obj.length; f<n; f++) {
            if(obj[f].Object==A) aIndex=k; 
            if(obj[f].Object==B) bIndex=k; 

            obj[f].index=k;
            entry[obj[f].index] = {left:i, right:-1};
            obj[f].left=i;
            //alert(obj[f].Object+','+obj[f].index+','+ obj[f].left);
            k++;
            i++;

            if (obj[f].Child) mptt(obj[f].Child);

            entry[obj[f].index].right = i;
            //alert(obj[f].Object+','+obj[f].index+','+entry[obj[f].index].right);
            obj[f].right=i;
            i++;
        }
        return obj;
    }

    if(entry[aIndex].left>entry[bIndex].left  &&  entry[aIndex].right<entry[bIndex].right) return true;
    else return false;
}

Demo: http://jsfiddle.net/bPu2V/

Answer 3

Here is a litle, self-contained recursive function that does what you want:

function linearDescendant(list, search, ancestor, _parent) {
  var i, item, found = false;

  for (i=0; i<list.length; i++) {
    item = list[i];
    item._parent = _parent;

    if (item.Object == search) {
      while (item._parent && item.Object != ancestor) {
        item = item._parent;
      }
      found = item.Object == ancestor;
    } else if (item.Child) { 
      found = linearDescendant(item.Child, search, ancestor, item);
    }
    if (found) break;
  }
  return found;
}

call it as:

linearDescendant(yourArray, "Sedan", "Civic")  // true
linearDescendant(yourArray, "Sedan", "Toyota") // false
linearDescendant(yourArray, "Prius", "Honda")  // false
linearDescendant(yourArray, "Yaris", "Car")    // true

Note that the function creates a _parent property in each of your nested objects. This is necessary to do the ancestor check once the searched object has been found.

Answer 4

It is some kind of a freaky hack, but you can use browser DOM-model to do the things. Do some kind of a 'precache' of your data struct into a DOM and traverse it with querySelectorAll or something similar (jQuery or else)

See jsFiddle - http://jsfiddle.net/SxCD6/2/

Answer 5

OK, I'll give this a shot: http://jsfiddle.net/nrabinowitz/UJrhK/

function Lineal_Descendant(child, parent) {
    // search in an array of objects
    function walk(array, search) {
        for (var x=0, found; x<array.length; x++) {
            found = visit(array[x], search);
            if (found) return found;
        }
        return false;
    }
    // search an object and its children
    function visit(obj, search) {
        // found search
        return obj.Object === search ? obj :
            // not found, but has children
            obj.Child ? walk(obj.Child, search) :
            // no children
            false; 
    }
    // find parent
    parent = walk(data, parent);
    // find child, converting to boolean
    if (parent) return !!walk(parent.Child || [], child);
}

There's probably a more elegant way to do this, but this will work. Note that you have nothing in your data structure to enforce unique names, so if you had two items at the same level with the same value for Object, the search might return unexpected results.